[BOJ] C++ 9935 문자열 폭발

9935번: 문자열 폭발

예제

mirkovC4nizCC44
C4

ans :
mirkovniz
---------------------------
12ab112ab2ab
12ab

ans :
FRULA

---

문자열에서 특정 문자열을 찾아 계속 삭제하는 문제이다. 삭제를 계속 반복하면서 삭제할 문자열이 남아있지 않을 때까지 완전탐색으로 풀면 시간초과가 뜬다. 따라서 처음 생각한 방법은 실제로 삭제를 하지는 않고 index만 다루어서 삭제했다 치고 푸는 것이었다. 이 방법은 삭제하는 시간은 줄지만 똑같이 완전 탐색이라 시간초과가 뜬다. 삭제할 문자열을 "." 등을 바꾸는 방법도 똑같이 시간초과가 뜬다.

 

따라서 완전 탐색이 아닌 방법으로 해결해야 하는데, 폭발문자열을 삭제하는 부분을 보면, 폭발 문자열이 나오기 전 부분의 문자열은 삭제를 하던 안 하던 변하지 않는다는 걸 알 수 있다. 다시 말하면 문자열의 삭제가 끝에서만 일어난다. 이 부분에서 스택을 떠올려서 스택으로 풀었다. 스택을 사용한다는 걸 생각하고 나면 구현은 쉽다.

/** 문자열 9935 문자열 폭발 **/
#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

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

    string str, explo;
    cin >> str >> explo;

    stack<char> s;
    reverse(explo.begin(), explo.end());

    for (int i = 0; i < str.length(); i++)
    {
        s.push(str[i]);

        // 스택의 탑에 있는 단어가 폭발 문자열 마지막 단어와 일치하면 꺼내서 점검한다.
        if (s.top() == explo[0] && s.size() >= explo.length())
        {
            string extracted;
            for (int j = 0; j < explo.length(); j++)
            {
                extracted.push_back(s.top());
                s.pop();
            }

            // 스택에서 꺼낸 문자열이 explo와 다르다면 다시 넣는다.
            if (extracted != explo)
            {
                for (int i = extracted.length() - 1; i >= 0; i--)
                    s.push(extracted[i]);
            }
        }
    }

    if (!s.empty())
    {
        string ans;
        // 스택에 남은 문자열 처리
        while (!s.empty())
        {
            ans.push_back(s.top());
            s.pop();
        }
        reverse(ans.begin(), ans.end());
        cout << ans;
    }
    else
        cout << "FRULA";
}