[BOJ9935] 문자열 폭발

[BOJ9935] 문자열 폭발

문제 설명

• 문자열이 주어지고, 폭발 문자열이 주어진다. 문자열안에 폭발문자열이 있으면 폭발문자열 부분은 지워지고, 지워진 문자열 좌우가 다시 합쳐진다.
• 합쳐진 후 다시 폭발문자열이 존재하면 같은 상황이 반복된다.
• 모든 폭발문자열이 지워졌을 때 남아있는 문자열을 출력하는 문제이다.

코드 리뷰

• 문자열을 앞에부터 deque에 넣었다. 그러다가 지금 넣는 문자가 폭발문자열의 맨 뒷글자와 같을 경우 폭발문자열 개수만큼 문자열을 비교해가며 두 문자가 같을 경우 pop_back을 하고, 그 문자를 스택에 쌓아둔다.
• 폭발문자열 개수만큼 확인을 하고, 스택에 있는 문자 개수가 폭발문자열 개수와 같을 경우엔 폭발문자열이 존재하였던 것이므로 다시 그 지점부터 문자열을 deque에 넣어가며 확인을 한다.
• 개수가 서로 다를 경우엔 폭발문자열과 다르다는 것이므로 스택에 쌓여있던 문자들을 다시 deque에 넣어준다.
• 이런식으로 문자열을 다 확인하고 나면 폭발 문자열이 다 지워지게 된다. 그럼 deque를 front부터 출력시켜주면 올바른 문자열이 나온다.

#include <iostream>
#include <string>
#include <deque>
#include <stack>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	deque <char> store;
	string s, bs;
	cin >> s;
	cin >> bs;
	for (const auto& c : s) {
		store.push_back(c);
		if (c == bs[bs.length() - 1]) {
			stack <char> tmp;
			for (int i = bs.length() - 1; i >= 0; i--) {
				if (!store.empty() && store.back() == bs[i]) {
					tmp.push(store.back());
					store.pop_back();
				}
				if (i == 0 && tmp.size() != bs.length()) {
					while (!tmp.empty()) {
						store.push_back(tmp.top());
						tmp.pop();
					}
				}
			}
		}
	}
	if (store.empty()) cout << "FRULA\n";
	else {
		while (!store.empty()) {
			cout << store.front();
			store.pop_front();
		}
		cout << "\n";
	}
	return 0;
}