[스택 / BOJ 9935 / C++] 문자열 폭발

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

9935번: 문자열 폭발

1) 만나면 폭발! 스택으로 생각하자.

내가 가장 먼저 풀었던 풀이는

#include <bits/stdc++.h>

using namespace std;

string S, bS;

vector<string> split(string input, string delimiter){
    vector<string> ret;
    long long pos = 0;
    string token = "";
    
    while ((pos = input.find(delimiter))!=string::npos) {
        token = input.substr(0, pos);
        ret.push_back(token);
        input.erase(0, pos+delimiter.length());
        
    }
    
    ret.push_back(input);
    return ret;
    
}

void go(string inputs){
    if(inputs==""){cout << "FRULA"; return;}
    
    vector<string> new_str_v = split(inputs, bS);
    
    if(!new_str_v.empty()){
        if(new_str_v[0] == inputs){
            cout << inputs;
            return;
        }else{
            string new_str = "";
            for(auto i : new_str_v) new_str+=i;
            new_str_v.clear();
            go(new_str);
        }
    }
    
    return;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> S >> bS;
    
    go(S);
    
    
}

 

이다. 문제 요건대로 그대로 구성했다. split하고, 폭탄문자열을 지우고, 남은 문자열 이어붙이고, 다시 split하고 ... 이를 반복한다.

이때 내가 잘못했던 부분은 공간복잡도와 시간복잡도가 무진장 커진다는 것이다.. 재귀적으로 split을 계속 호출하니깐 vector<string>이 계속 선언돼 공간을 많이 차지한다. 게다가 split자체에서 find함수 자체가 O(N)의 시간복잡도이므로, 재귀적으로 호출하면 시간복잡도가  꽤나 커진다. 즉, 다른 방법을 생각해야한다 !!

(2023. 5. 18 수정)

 

-----

 

요즘 혼자 푸는 문제가 없다 ㅠㅠ 더 연습해야겠다

 

우선 string을 이용하여 풀어야하는데, 가장쉽게는 이중 For문을 이용해서 풀면 된다.

 

해당 폭발 문자열을 찾아 제거하고, 문자열 이어붙이고 .... 계속해서 반복하는 것이다.

 

그러나 시간복잡도가 100만 * 100만 ! 너무 크다. 따라서 한번에 해결할 방법을 찾아야한다.

 

우선 주어진 string을 잘게 쪼개, char로 하나씩 보자. 해당 char을 스택에 차곡차곡 모은다. 그러다 폭발 문자열의 마지막 문자와 스택의 Top()이 같게 되면 스택에 폭발문자열이 들어갔는지 pop을 해가며 확인한다! 

(이때, 뽑아낸 문자들을 문자열로 저장하면, 뒤집어 저장되므로, 비교를 위해 reverse를 해야한다.)

 

폭발 문자열인 char모음이 생기면, 이를 저장을 하지 않는다. 그러나 폭발 문자열이 아니었다면, 빼낸 문자열을 다시 넣어줘야한다.

 

바로 코드로 넘어가서 보자.

 

#include <bits/stdc++.h>

using namespace std;

string S, bS, ret;
stack<char> s;



int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> S >> bS;
    
    for(auto i : S){
        s.push(i);
        
        if(s.size() >= bS.size() && s.top() == bS[bS.size()-1]){
            string tmp = "";
            for(char l : bS){
                tmp += s.top();
                s.pop();
            }
            
            reverse(tmp.begin(), tmp.end());
            
            if(bS!=tmp){
                for(auto k : tmp){
                    s.push(k);
                }
            }
        }
        
        
    }
    
    if(s.size()){
        while(s.size()){
            ret += s.top();
            s.pop();
        }
        reverse(ret.begin(), ret.end());
        cout << ret << '\n';
    } else{
        cout << "FRULA" << '\n';
    }
}