문자열 폭발 (9985)

---

문제 정의

• 문자열이 폭발 문자열을 포함하고 있는 경우, 모든 폭발 문자열이 폭발한다. 남은 문자열은 순서대로 이어 붙여져 새로운 문자열을 만든다.
• 만약 새로 만들어진 문자열이 폭발 문자열을 가지고 있는 경우 모든 폭발 문자열을 폭발시킨다.
• 폭발 문자열이 존재하지 않을 때까지 위 과정을 반복한다.

입력

• 첫째 줄에 문자열이 주어진다. ( 1<= 길이 <=1000000)
• 둘째 줄에 폭발 문자열이 주어진다.(1<= 길이 <=36)
• 문자열은 0~9와 소문자,대문자 알파벳으로 이루어진 문자열이다.

출력

• 첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
• 만약 남은 문자열이 없다면 FLURA를 출력한다.

---

Solution

STACK을 이용하여 풀면 아주 간단하게 해결되는 문제다.
Backjoon사이트에서 제공하는 예제를 하나 보자.
입력

mirkovC4nizCC44
C4

먼저 mirkovC4까지만 보면 C4가 폭발 문자열이므로 사라진다.
그러면 mirkov가 남고 나머지 nizCC44를 이어붙여
mirkovnizCC44가 된다.
여기서 다시
mirkovnizCC4까지만 보게 되면 제일 끝에 폭발 문자열이 있으므로 터쳐준다.
mirkovnizC가남고 뒤에 문자열인 4를 다시 붙여주면 다음과 같다.
mirkovnizC4
여기서도 역시 마지막 문자열이 폭발 문자열이므로 터쳐준다. 그럼 남은 문자열은 다음과 같다.
mirkovniz
더이상 폭발 문자열이 포함되지 않았으므로 mirkovniz를 출력하면 된다.
위의 순서를 정리해보면 다음과 같다.

• 현재 저장한 문자열에 폭발 문자열이 있지 않다면 계속해서 문자열을 하나씩 추가하며 저장한다.
• 만약 현재까지 저장한 문자열에 폭발 문자열이 존재한다면 끝에 부터 있으므로 폭발 문자열을 폭파한다.
  ex) mirkovnizC -> mirkovnizC4 -> mirkovniz
• 위 과정을 반복하여 문자열을 끝까지 탐색한다.

---

정답 코드

#include <iostream>

using namespace std;

char arr[1000000];
 // 폭발할 문자열과 현재 저장한 문자열의 끝에있는 문자열을 비교 
bool compare(string key, int p) {
	string a = ""; // 비교할 문자열 생성
	for (int i = key.length(); i > 0; i--) {
		a += arr[p - i];
	}
	if (a == key) return 1;
	else return 0;
}

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

	string temp, key; // key - 폭발 문자열, temp - 탐색할 문자열
	cin >> temp >> key;
	int p = 0; // 문자열의 개수를 확인할 변수
    
	// 문자열을 처음부터 끝까지 탐색 
	for (int i = 0; i < temp.length(); i++) {
		arr[p++] = temp[i];
		if (p >= key.length()) {
			if (compare(key, p)) // 만약 문자열의 끝이 폭발 문자열인 경우
		 		p -= key.length(); // 폭파 
		}
	}

	if (!p) // 남아있는 문자열의 개수 확인 
		cout << "FRULA\n";
	else { // 남아있는 문자열 존재하므로 출력
		for (int i = 0; i < p; i++) {
			cout << arr[i];
		}
		cout << '\n';
	}


	return 0;
}