백준 9935번 : 문자열 폭발

문제 접근

---

처음에는 입력 문자열에서 폭발 문자열을 찾은 뒤 삭제하고 삭제한 위치의 전부터 다시 탐색하는 방법으로 O(입력 문자열 길이) 로 풀려고 했는데 문자열을 삭제하는데 시간이 더 오래 걸려 좋은 방법이 아니라고 생각했다. 문자열 알고리즘을 찾아보던 중 보이어-무어 알고리즘에 대해 알게 되어 이 알고리즘의 접근 방법을 살짝 이용했다.

 

보이어-무어 알고리즘은 문자열을 오른쪽에서 왼쪽으로 비교하고, 이동은 왼쪽에서 오른쪽으로 하는 방식인데 오른쪽 끝의 문자가 일치하지 않고, 끝 문자가 비교 문자열에 존재하지 않으면 비교 문자열 길이만큼 이동하는 알고리즘이다. 끝 문자가 비교 문자열 내에 존재하는 것까지 확인할 필요는 없어보였고, 스택에 넣다가 끝 문자와 같은 문자가 나오면 앞 문자열을 비교한 뒤 비교 문자열과 같으면 그 길이만큼 pop() 하고, 다시 쌓는 방식으로 구현했다. 풀이 후 다른 사람 코드를 확인해보니 더 깔끔하고, 스택을 이용하지 않아도 되는 코드가 있어서 그 방식으로 다시 구현했다.

 

1. ans 배열의 idx 번째 문자에 입력된 문자열 src 의 i 번째 문자를 대입한다.

2. idx 번째 문자가 폭발 문자열 exp 의 마지막 문자와 같다면, exp 크기가 idx 크기보다 큰 지 확인한다.

3. 크다면 계속 진행하고, 작거나 같다면 ans 와 exp 를 비교한다.

4. ans 의 일부분이 exp 와 같다면 idx 를 exp 의 크기만큼 감소한다. ( 폭발 문자열 제거 )

5. idx 가 0이면 "FRULA" 를 출력하고, 0이 아니라면 ans 를 출력한다.

 

정리하자면 입력 문자열을 ans 배열에 차례대로 쌓다가 폭발 문자열의 끝자리 문자와 같은 문자가 확인되면 폭발 문자열의 일부인지 확인한 뒤 폭발 문자열이라면 쌓을 위치를 가리키는 idx 를 폭발 문자열 길이만큼 감소해서 제거하는 것이다.

 

 

문제 코드

---

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
    	cin.tie(0);
    
	int idx = 0;
	string src, exp;
	char ans[1000001];
	
	cin>>src>>exp;
	
	for(int i=0; i<src.size(); ++i)
	{
		ans[idx++] = src[i];
		
		if(ans[idx-1] == exp[exp.size()-1])
		{
			if(idx<exp.size())
				continue;
			
			bool check = true;
			
			for(int j=0; j<exp.size(); ++j)
			{
				if(ans[idx-j-1] != exp[exp.size()-j-1])
				{
					check = false;
					break;
				}
			}
			
			if(check)
				idx-=exp.size();
		}
	}
	
	if(!idx)
		cout<<"FRULA\n";
	else
	{
		for(int i=0; i<idx; ++i)
			cout<<ans[i];
		cout<<'\n';
	}
}