[BOJ] 9935번_문자열 폭발_문자열 (C++)

[문제]

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

문자열에 폭발 문자열을 포함하고 있을 경우 폭발 문자열이 사라지며, 남은 문자열을 이어 다시 문자열을 만든다. 모든 폭발이 끝난 후에 남은 문자열을 출력하고, 문자열이 남아 있지 않을 경우엔 "FRULA"를 출력하는 문제이다.

[사용 알고리즘]

문자열

[풀이 핵심]

• 폭발 문자열이 사라지고 남은 문자열을 이어 다시 문자열을 만들 때 폭발 문자열이 생길수도 있다.
• 문자열의 길이가 최대 1000000이므로 문자열을 모두 입력받고 폭발 문자열을 찾는 식으로 풀면 시간초과가 난다.

1. 문자열을 char단위로 한 문자씩 입력받는다.
2. 입력받은 문자가 폭발 문자열의 마지막 문자일 경우 폭발 문자열인지 확인한다.
3. 폭발 문자열일 경우 문자열에서 지워준다.

[코드]

//boj9935번_문자열 폭발_문자열

#include<iostream>
#include<string>

using namespace std;

int main() {
	string str, explosion;
	cin >> str;
	cin >> explosion;

	string result = "";

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

		if (str[i] == explosion[explosion.size() - 1]) {
			string temp = "";
			for (int j = explosion.size() - 1; j >= 0; j--) {
				temp += result[result.size() - 1 - j];
			}

			if (temp == explosion) {
				result.erase(result.size() - explosion.size(), explosion.size());
			}
		}
	}

	if (result == "") {
		cout << "FRULA";
	}
	else {
		cout << result;
	}

	return 0;
}