BOJ 9935 - 문자열 폭발

Problem
https://www.acmicpc.net/problem/9935

Solution

처음에는 정규식의 replace를 사용해서 해결하려 했다.

#include <bits/stdc++.h>
using namespace std;

int main(void) {

	string s,t;
	cin >> s;
	cin >> t;
	while (1) {
		string temp = regex_replace(s, regex(t), "");
		if (temp != s) s = temp;
		else break;
	}
	if (!s.empty()) cout << s << '\n';
	else cout << "FRULA" << '\n';
	return 0;
}

결과는 잘 나왔으나, 문자열 제한이 100만인만큼, 치환을하고, 다시 선형적으로 탐색하고 하는데 시간이 많이 걸렸던 탓인지 시간초과가 떴다.

조금 알아보니 이 문제의 분류가 스택으로 분류되어있다는걸 알았다. 스택을 활용한다는것은 값을 빼오고, 바로바로 검사한다는 스타일일거라고 생각했고 그와 비슷하게 문제를 풀어보았다.

#include <bits/stdc++.h>
using namespace std;

int main(void) {

	string s,t,str;
	cin >> s;
	cin >> t;
	
	for (int i = 0; i < s.size(); i++) {
		bool boom = true;

		str += s[i];
		if (str.size() >= t.size()) {
			int k = 0;
			for (int j = str.size() - t.size(); j < str.size(); j++) {
				if (str[j] != t[k++]) boom = false;
			}

			if (boom) { //폭발!
				for (int j = 0; j < t.size(); j++) {
					str.pop_back();
				}
			}
		}
	}

	if (str.empty()) cout << "FRULA\n";
	else cout << str << '\n';

}

문자 하나하나를 계속 빼오고, 폭발 문자열(t) 과 길이가 같아지면 그때마다 검사를 한다. 문자열이 완전히 같다면 string에서 pop을 해서 문자열을 제거해주고, 이러한 과정을 반복한다.

예로 CC44가 문자열이고 폭발 문자열이 C4라고 생각해보자.
CC까지 빼오면 폭발 문자열과 크기가 같기때문에 이때 검사를 진행한다.
결과는 아닐것이고 이후에 CC4까지 빼와본다.
C4의 길이는 2이고, 앞의 CC는 아닌것을 이미 알고있기때문에 새로운 문자열인 C4를 검사해본다. 이런식으로 계속 검사하면 정답을 도출할 수 있다!