🔍 9935 문자열 폭발

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

---

🤔 풀이

• 문자열의 문자 하나하나를 탐색하고 출력하기 위해 스택을 사용한다. (검사 스택)

• 해당 문자열의 폭발 문자열 하나를 제거하면, 또 다른 폭발 문자열이 생길 수 있다.
  (예. 폭발 문자열 : xyz, 문자열 : abxyxxyzyzz -> abxyxyzz -> abxyz)
  따라서 입력받은 문자열을 탐색할 때, 폭발 문자열의 마지막 문자와 똑같은지 검사해야 한다. (폭발 문자열의 첫번째 문자와 같은지 확인 후, 그 다음에 들어오는 문자를 보고 처리하면 해당 폭발 문자열이 없어진 후, 새로 생기는 폭발 문자열에 대해 검사할 수 없다.)

• 문자열 탐색 중에, 만약 그때의 문자와 폭발 문자열의 마지막 문자와 똑같다면, 해당 문자와 앞 문자들의 조합이 폭발 문자열인지 검사한다. 현재 검사스택에서 마지막부터(=폭발문자열의 마지막 문자를 가짐) 차례대로 임시 스택에 집어넣는다. 만약 도중에 폭발문자열과 같지않음이 판단된다면, 그대로 임시스택에서 문자를 빼내어 다시 검사 스택에 넣는다. 폭발문자열과 같음이 판단된다면, 해당 문자열들은 폭발되므로 검사 스택에 넣지 않고, 임시 스택을 비워준다.
  

---

📝 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string input;
string ex;

int main() {
    cin >> input >> ex;
    
    vector<char> ans;
    vector<char> temp;

    for (int i = 0; i < input.size(); i++) {
        ans.push_back(input[i]);

        if (ans.back() == ex[ex.size()-1] && ans.size() >= ex.size()) {
            int j;
            for (j = ex.size()-1; j >= 0; j--) {
                if (ans.back() == ex[j]) {
                    temp.push_back(ans.back());
                    ans.pop_back();
                }
                else break;
            }

            if (j == -1) {
                while (!temp.empty()) temp.pop_back();
            }
            else {
                while (!temp.empty()) {
                    ans.push_back(temp.back());
                    temp.pop_back();
                }
            }
        }
    }

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