[백준] 9935번 - 문자열 폭발 [C++]

---

문제

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

9935번: 문자열 폭발

---

발상

문제자체가 스트링에서 특정 단어를 찾는 것이기에 string.find를 사용하여 npos가 나올때까지 반복을 하면 되지 않을까? 하고 코드를 적었다.

 

하지만 골드문제 답게 예상대로 string.find는 길이가 길어질수록 연산이 많아져서 시간초과가 떴다.

 

그래서 어떻게 하면 시간을 줄일 수 있을까? 생각했고,

스트링을 스택처럼 사용해서 글자 하나하나를 넣고, 만들고 폭탄과 같은 문자열을 갖는지 확인하는 check스트링을 만든다음 스트링을 잘라서 만약 폭탄과 같으면 erase하는 형태로 가면은 시간을 줄일 수 있지 않을까? 생각했다.

---

소스코드

#include <iostream>
#include <string>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	string a, b, answer, check;
	cin >> a >> b;
	for (int i = 0; i < a.length(); i++)
	{
		answer += a[i];
		if (answer.length() >= b.length())
		{
			check = "";
			for (int i = b.length(); i > 0; i--)
				check += answer[answer.length() - i];
			if (check == b)
				answer.erase(answer.length() - b.length());
		}
	}
	if (answer == "")
		cout << "FRULA";
	else
		cout << answer;
}