[BOJ/C++] 9935 문자열 폭발

문제

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

풀이

처음에 find로 폭발 문자열 제거하는 방식으로 풀이했는데 O(N)이라 시간초과 발생
stack 개념을 이용해야 한다.

💡tmp 문자열을 stack처럼 활용

1. tmp에 하나씩 push

2. tmp의 끝 문자와 폭발 문자열의 끝 문자가 같은 경우
   2-1. tmp 길이가 폭발 문자열 길이보다 짧으면 continue
   2-2. tmp에서 폭발 문자열 길이만큼 문자 비교

3. 폭발 문자열이 존재한다면, 폭발 문자열 크기만큼 tmp에서 pop

4. tmp가 비어있을 경우 FRULA 출력, 그렇지 않을 경우 tmp 출력

코드

#include <iostream>
#include <string.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str, bomb, tmp = "";
	cin >> str >> bomb;

	for (int i = 0; i < str.size(); i++) {
		tmp += str[i];

		if (tmp.back() == bomb.back()) {
			bool mark = true;
			if (tmp.size() < bomb.size())	continue;
			for (int j = 0; j < bomb.size(); j++) {
				if (tmp[tmp.size() - bomb.size() + j] != bomb[j]) {
					mark = false;
					break;
				}
			}

			if (mark) {
				for (int j = 0; j < bomb.size(); j++)	tmp.pop_back();
			}
		}
	}

	if (tmp.empty())
		cout << "FRULA" << '\n';
	else {
		cout << tmp << '\n';
	}

	return 0;
}