[백준] 9935번 문자열 폭발

문제 및 입출력

문제 접근

stack으로 구현해서 풀었다가 시간 초과가 나서 다른 사람 블로그를 참고하였다,,,
내가 처음에 접근한 방법은 첫번째 문자부터 차근차근 비교를 하는 거 였는데, 해당 하는 것과 동일하게 접근을 한다면, 시간 초과가 나는 거 같았다.
따라서, 폭발 문자열의 마지막 문자와 비교하여서, 같다면 이전 것들을 비교하여, 폭발 문자열을 찾는 방법이다.
이전 문자열을 따로 꺼낼 필요는 없고 stack내에서 비교하면 되서, 시간이 상대적으로 save가 되었다.
시간 복잡도는 O(문자열 길이(n) * bomb문자열 길이(m))으로 m은 최대 36이기 때문에 상쇄되어, O(n) 이 나올 거 같다.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <string>

using namespace std;
vector<char> st;

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

    string result = "";
    string str;
    cin >> str;
    string bomb;
    cin >> bomb;
    int bomb_len = bomb.length();
    int str_len = str.length();
    vector<char> temp;
    for(int i = 0 ; i < str_len ; i++){
        temp.push_back(str[i]);
        if(temp.size() < bomb_len) continue;
        if(temp.back() == bomb[bomb_len - 1]){
            bool check = true;
            for(int j = 2 ; j <= bomb_len ; j++){
                if(temp[temp.size() - j] != bomb[bomb_len - j]) {
                    check = false;
                    break;
                }
            }
            if(check){
                temp.erase(temp.end() - bomb_len , temp.end());
            }
        }
    }
    if(temp.empty()) result = "FRULA";
    else{
        for(int i = 0 ; i < temp.size() ; i++){
            result += temp[i];
        }
    }
    
    cout << result << "\n";
}