[C++] 9935: 문자열 폭발

정답코드

#include <iostream>
#include <queue>
using namespace std;

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

	string str;
	string boom;

	cin >> str;
	cin >> boom;

	deque<char> q;

	for (int i = 0; i < str.size(); i++) {
		q.push_back(str[i]);
		if (q.size() >= boom.size()) {
			if (q.back() == boom[boom.size() - 1]) {
				int check = 0;
				for (int i = 0; i < boom.size(); i++) {
					if (q[q.size() - 1 - i] == boom[boom.size() - 1 - i]) check++;
				}

				if (check == boom.size()) {
					for (int i = 0; i < boom.size(); i++) q.pop_back();
				}
			}
		}
	}

	if (q.empty()) { cout << "FRULA"; }
	else {
		for (int i = 0; i < q.size(); i++) { cout << q[i]; }
	}
}

deque에 문자열을 한 글자씩 넣으면서, 만약 deque의 마지막 글자가 폭발 문자열의 마지막 글자와 같으면 폭발 문자열인지 역순으로 체크하는 방식으로 풀었다.

오답

#include <iostream>
using namespace std;


bool ch(string str, string boom) {
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == boom[0]) {

			int check = 0;

			for (int j = 0; j < boom.length(); j++) {
				// str 길이 초과면 break
				if (i >= str.length()) break;
				else if (str[i + j] != boom[j]) break;

				check++;
			}

			if (check == boom.length()) return true;
		}
	}
	return false;
}

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

	string str;
	string boom;

	cin >> str;
	cin >> boom;

	string ans = "";

	while (true) {
		for (int i = 0; i < str.length(); i++) {
			if (str[i] == boom[0]) {

				int check = 0;

				for (int j = 0; j < boom.length(); j++) {
					// str 길이 초과면 break
					if (i >= str.length()) break;
					else if (str[i + j] != boom[j]) break;

					check++;
				}

				if (check == boom.length()) i += (boom.length() - 1);
				else ans += str[i];
			}
			else {
				ans += str[i];
			}
		}

		// 빈 문자열이면 break
		if (ans == "") break;
		// 문자열에 폭발 문자열이 없으면 break
		else if (!ch(ans, boom)) break;
		// break 조건에 해당이 없으면, str과 ans 초기화하고 반복
		else {
			str = ans;
			ans = "";
		}
	}
	if (ans == "") cout << "FRULA";
	else cout << ans;
}

40%쯤에서 시간초과가 발생했다
문자열을 하나씩 체크하는걸 반복하는게 문제인거 같아서 반복문 없이 문자열을 한번만 체크하는데 초점을 두고 코드를 다시 짰다