백준 9935번 문자열 폭발

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/9935

 

 

 

9935번: 문자열 폭발

 

 

이번 문제는 자료구조 문제였습니다.

 

처음에는 string의 find 함수와 erase 함수를 사용하여 문제를 풀어서 시간초과가 났습니다. 😅 

 

 

 

 

《문제 풀이》

 

1. 입력 문자열을 하나씩 결과 문자열에 삽입

2. 결과 문자열의 마지막 문자가 폭발 문자열의 마지막 문자와 같으면 폭탄 문자열을 제거할 지를 검사

     (1) 결과 문자열의 마지막 문자부터 폭발 문자열의 길이까지 비교

     (2) 결과 문자열의 문자와 폭발 문자열의 문자가 다르다면 flag = false

     (3) flag = true 이면 (결과 문자열에 폭발 문자열이 있으면) 폭탄 문자열 제거 

3. 1, 2를 입력 문자열의 길이만큼 반복

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 1000000

using namespace std;

char result[MAX];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string str, bomb;
	cin>>str>>bomb;
	
	int idx = 0;
	int len = bomb.length(); // 폭탄 문자열의 길이  
	
	for(int i=0; i<str.length(); i++) {
		result[idx++] = str[i];
		
		// 폭탄 문자열의 존재 가능성  
		if(result[idx - 1] == bomb[len - 1]) {
			bool flag = true;
			
			for(int j=0; j<len; j++) {
				if(result[idx - j - 1] == bomb[len - j - 1])
					continue;
				
				flag = false;
				break;
			}
			if(flag)
				idx -= len; // 폭탄 문자열 제거  
		}
	}

	if(idx == 0)
		cout<<"FRULA";
	else {
		for(int i=0; i<idx; i++)
			cout<<result[i];
	}
	
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

baekjoon - 정답 화면