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

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

TLE 때문에 시간을 많이 쓴 문제.

연쇄적으로 폭발하는 경우를 고려해서 작성해야 했다.

최악의 경우 반례:

aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbb.....

와 같은 꼴이면 $O(N^2)$이 소요된다.

문제 접근

연쇄 폭발을 고려해야 했기 때문에,

문자열 $S$의 부분 문자열을 스택에 하나하나 넣으면서

현재 문자열이 폭발 문자열 $T$의 마지막 문자라면 폭발이 가능한 경우이기에

앞 스택에서 꺼내면서 폭발이 일어날 수 있는지 확인해주었다.

코드는 다음과 같다.

(많은 생각을 해봤지만 다른 조건을 더 추가하면 코드가 복잡해질것 같아,

이 코드가 최선의 선택이라고 생각하고 작성했다. 다른 좋은 방법이 있으면

말씀 부탁드립니다.)

#include <bits/stdc++.h>
using namespace std;

deque<char> dq;
string s,t;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> s >> t;
    char l=t[t.length()-1];
    for(int i=0;i<s.length();i++){
        if(s[i]==l){
            if(dq.size()<t.length()-1){dq.push_back(s[i]);continue;}
            stack<char> tmp;
            tmp.push(s[i]);
            for(int i=1;i<t.length();i++){
                if(dq.back()!=t[t.length()-(i+1)]) break;
                tmp.push(dq.back()); dq.pop_back();
            }
            if(tmp.size()!=t.length()) while(!tmp.empty()){
                dq.push_back(tmp.top());
                tmp.pop();
            }
        }
        else dq.push_back(s[i]);
    }
    if(dq.empty()) cout << "FRULA";
    while(!dq.empty()){
        cout << dq.front(); dq.pop_front();
    }
    return 0;
}