BOJ 9935 : 문자열 폭발

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

O(nk)로 풀어야 한다.

스택으로 한 문자씩 넣은 뒤 문자가 폭발 문자열의 마지막 문자열이랑 같다면 그 전 문자열들을 확인해서 제거하면 된다.

쉬운 문제.

#include <bits/stdc++.h>
#define MEM 1000009
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
string s,t;
int main()
{
    sanic; cin.tie(0);
    cin >> s >> t;
    stack<char> sc;
    for(int i=0; i<s.size(); i++){
        sc.push(s[i]);
        if(s[i]==t[t.size()-1] && sc.size()>=t.size()){
            string v;
            for(int j=0; j<t.size(); j++)
                v += sc.top(), sc.pop();
            reverse(v.begin(), v.end());
            bool c=1;
            for(int j=0; j<v.size(); j++)
                if(v[j]!=t[j]){
                    c=0;
                    break;
                }
            if(!c)
                for(int j=0; j<v.size(); j++)
                    sc.push(v[j]);
        }
    }
    string ans;
    if(sc.empty()){
        cout << "FRULA";
        return 0;
    }
    while(!sc.empty()){
        ans += sc.top();
        sc.pop();
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
}