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

문제

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

---

문제 요약

문자열과 폭발 문자열이 주어진다.

 

문자열이 폭발 문자열을 포함하고 있다면, 해당 문자열을 사라지고 남은 문자열이 합쳐진다.

 

새로 생긴 문자열에 폭발 문자열이 포함되어 있다면, 다시 해당 문자열은 사라진다.

 

폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

 

모든 폭발이 끝난 후, 남아 있는 문자를 출력하고, 없다면 FRULA를 출력한다.

---

코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string text, boom;

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

    cin >> text >> boom;

    int n = text.size();
    int m = boom.size();

    string st = "";

    for (int i = 0; i < n; i++) {
        // 일단 스택에 push
        st.push_back(text[i]);

        // 탐색 문자가 폭발 문자열의 마지막 문자 && 스택 내 원소 수가 폭발 문자열 개수 이상
        if (text[i] == boom[m - 1] && st.size() >= m) {

            // 폭발 문자열 길이만큼 스택에서 pop
            string tmp;
            for (int j = 0; j < m; j++) {
                tmp.push_back(st.back());
                st.pop_back();
            }

            // pop한 문자열 뒤집기
            reverse(tmp.begin(), tmp.end());

            // pop한 문자열과 폭발 문자열이 다르면, 다시 스택에 push
            if (tmp != boom) {
                st += tmp;
            }
        }
    }

    if (st.empty()) {
        cout << "FRULA";
    }
    else {
        cout << st;
    }

    return 0;
}

---

코드 설명

1. 입력 문자열을 앞에서부터 차례로 접근하고, 스택에 하나씩 삽입한다.

 

2. 만약 스택에 삽입한 문자가 폭발 문자열의 마지막 문자라면, 폭발 문자열 길이만큼 스택에서 pop한다.

- pop한 문자열이 폭발 문자열과 다르면, 다시 스택에 push한다.

 

3. 스택에 남아 있는 문자를 출력한다.