[Gold 4] 9935 문자열 폭발

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

 

처음 문제를 해결할 때 find 함수와 erase함수를 사용했다.

하지만 find 함수에 필요한 시간과 erase함수에 필요한 시간 때문에

최대 길이의 문자열일 경우 시간 초과가 발생하였다.

 

따라서 스택을 사용해서 문제를 해결하였다.

 

스택을 사용해 문자열을 폭발 시키는 과정은 다음과 같다.

1. 스택에 문자열에 있는 문자를 순차적으로 삽입한다.

2. 스택에 들어있는 문자의 개수가 폭발 문자열의 길이와 같거나 클 경우

• 폭발 문자열의 길이만큼 스택에서 문자를 꺼낸다
• 꺼낸 문자열과 폭발 문자열이 일치한 경우 스택에서 제거한다.

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string target;
string bomb;
vector<char> v;

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

    cin>>target;
    cin>>bomb;

    for(int i = 0;i<target.length();i++){
        v.push_back(target[i]);

        if(v.size() >= bomb.length()){
            string str = "";
            for(int i = bomb.length();i>0;i--)
                str += v[v.size() - i];

            if(str == bomb){
                for(int i = 0;i<str.length();i++)
                    v.pop_back();
            }
        }
    }
    if(v.empty()){
        cout<< "FRULA";
        return 0;
    }
    for(int i = 0;i<v.size();i++)
        cout<<v[i];
}