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

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

 

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

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

    string s, bomb;
    cin >> s >> bomb;

    stack<char> stk;
    int n = bomb.size();

    for (char c: s) {
        if (c == bomb[n - 1]) {
            for (int i = n - 2; i >= 0; i--) {
                if (stk.empty()) {
                    for (int j = i + 1; j <= n - 1; j++) {
                        stk.push(bomb[j]);
                    }
                    break;
                }
                if (stk.top() == bomb[i]) {
                    stk.pop();
                } else {
                    for (int j = i + 1; j <= n - 1; j++) {
                        stk.push(bomb[j]);
                    }
                    break;
                }
            }
        } else {
            stk.push(c);
        }
    }

    string ans = "";
    while (!stk.empty()) {
        ans += stk.top();
        stk.pop();
    }
    
    if (ans == "") {
        cout << "FRULA\n";
    } else {
        reverse(ans.begin(), ans.end());
        cout << ans << '\n';
    }
}

주의할 점 1: 스택을 사용해야 한다.

문자열을 쭉 읽고 폭발시키고, 폭발으로 인해 새롭게 만들어진 문자열에 대해서 또 다시 읽고 다시 폭발시키고...를 반복하면 당연히 시간이 너무 오래걸린다. 그래서 스택을 사용해야 한다! 스택을 사용하면 읽으면서 연쇄적인 폭발까지 전부 처리할 수 있기 때문에 한번만 읽어도 된다. (단, 이것은 "폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다"라는 조건이 있기 때문이다... 아마도...)

주의할 점 2: 문자를 문자열 앞에 붙이는 것이 아니라 뒤에 붙인 후 뒤집어 주어야 한다. 

이건 피보나치 수 4 문제를 풀 때도 중요했던 내용이다. ans = stk.top() + ans; 이런식으로 하면 문자 복사가 일어나 문자열이 길어질수록 시간이 매우 오래 걸리게 된다. (실제로 이 문제에서 시간 초과가 나온다.) 반대로 ans += stk.top(); 이런식으로 하면 C++에서 자동적으로 스택을 처리하듯 해주기 때문에 시간이 훨씬 덜 걸린다.

주의할 점 3: 스택이 비어있음을 발견했을 때도 문자열을 다시 복구해주어야 한다. (이건 나만 주의하면 될 듯 ^___^)

너무나도 당연한 말이지만... 난 이것때문에 몇십분을 헤맸다. 아래의 코드와 같이 문자열을 다시 복구해주는 작업을 else에서만 하고 if (stk.empty()) 일 때는 안 해주어서 거의 99퍼에서 틀렸다. 

for (int j = i + 1; j <= n - 1; j++) {
    stk.push(bomb[j]);
}

c3c3c
3c3
output: c
answer: cc

위의 반례는 물론 "폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다"라는 조건에 위배되기 때문에 실제 채점 케이스에 있지는 않겠지만, 주의할 점 3에서의 문제를 찾는데에 도움이 되었기에 적는다.

(AC)

 

---

 

반례 찾는다고 게시판을 엄청 돌아다녔는데 웃긴 글이 되게 많다. 그 중에서 "눈물샘 폭발입니다..", "문자열폭발 풀다 제머리가 폭발할것 같습니다." 등의 글이 공감이 많이 되었다... ^__ㅜ