백준 / 9935 / 문자열 폭발 / C++

문제 링크 : https://www.acmicpc.net/problem/9935

#include <bits/stdc++.h>

using namespace std;

string str;
string bomb;
int bomblength;
int strlength;
/*bool check(stack<char> S)
{
    for (int i = bomblength - 1; i >= 0; i--)
    {
        if (S.top() != bomb[i])
        {
            return false;
        }
        S.pop();
    }
    return true;
}*/

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    stack<char> S;
    cin >> str >> bomb;
    char stand = bomb.back();
    bomblength = bomb.length();
    strlength = str.length();
    for (int i = 0; i < strlength; i++)
    {
        S.push(str[i]);
        if (str[i] == stand)
        {
            if (S.size() >= bomblength)
            {
                string tmp = "";
                for (int i = 0; i < bomblength; i++)
                {
                    tmp += S.top();
                    S.pop();
                }
                reverse(tmp.begin(), tmp.end());

                if (tmp != bomb)
                {
                    for (char c : tmp)
                    {
                        S.push(c);
                    }
                }
            }
        }
    }
    if (S.empty())
    {
        cout << "FRULA";
    }
    else
    {
        string result = "";
        while (!S.empty())
        {
            result += S.top();
            S.pop();
        }
        reverse(result.begin(), result.end());
        cout << result;
    }
    return 0;
}

진짜... PS를 시작한지 꽤 됐다고 할 수는 없지만 지금까지 풀어본 문제들 중에서는 제일 어려웠던 것 같다... 플레 문제들보다도 더 시행착오가 많았다

첫 시도는 문자열 자체의 인덱스 기반으로 풀어보려고 했다. 하지만 한번의 폭발 이후로 뒷 부분의 문자열을 끌어오는 로직 자체가 O(N)이라 시간복잡도 때문에 시간 초과.

두번째 시도는 스택을 사용해서 check라는 함수를 만든 후, 폭발 문자열은 중복된 문자가 사용되지 않는다는 점을 이용해 폭발 문자열의 맨 마지막 문자열이 스택에 삽입될 때 check함수에 스택을 call by value로 넘겨줘서 폭발문자열 길이만큼 pop하면서 다른 값이 있다면 false, 아니라면 true를 반환하는 함수로 접근했지만... 이것도 46% 근처에서 시간초과를 받았다.

마지막 시도에서는 check함수를 계속 불러오는 것이 시간초과를 유발한다고 가정, 함수 자체를 불러오지 않고 로직 자체를 main으로 가져오되 문자열 기반 접근(임시 string을 선언하고 스택에서 pop을 하며 임시 string을 길이만큼 채운 뒤 reverse 하고 폭발 문자열과 같다면 그대로 계속 진행, 아니라면 다시 스택에 삽입)했다. 그러니 AC를 받았다.

근래에 푼 문제들 중 개인적으로는 제일 어려웠던 것 같다... 로직이 틀린 건 아닌 것 같은데 시간초과를 계속 먹으니까...