[백준 9935] 문자열 폭발

문제링크 : https://www.acmicpc.net/problem/9935

복기

1. 스택을 쓸 생각을 하지 못 했다.
2. 마구잡이로 구현해서 메모리 초과 발생

문제유형 : 자료구조(스택)

자료 구조 : 스택 
문자열

---

처음 접근한 방법은 아래와 같다. 단순구현 방식으로 풀었는데, 메모리 초과가 발생.

1. 최초풀이 : split을 이용한 단순 구현

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

// 1. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 
// 2. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
// 3. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
// 4. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
// 5. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
// restriction : 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
string str;
string bomb;

void input() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    str.reseriossve(1000004);//미리 할당  
    cin >> str >> bomb;
}

string removeBomb(string str, string bomb) {
    string res = "";
    long long pos = 0;
    string token = "";
    while ((pos = str.find(bomb)) != string::npos) {
        token = str.substr(0, pos);
        res += token; 
        str.erase(0, pos + bomb.length());
    }
    res += str; 
    return res;
}

string explosion(string str, string bomb) {
    if (str.length() == 0) return "FRULA";
    else if(str.find(bomb) == string::npos ) return str; // exit condition
    else return explosion(removeBomb(str, bomb), bomb);// 폭발 문자열이 있는 경우
}

void solve() {
    input();
    cout << explosion(str, bomb);
}

int main() {
    solve();
    return 0;
}

알고리즘 분류를 열어보니 자료구조, 스택이 나와 있다. 스택을 써야 한다는 힌트를 얻고, 어디에 스택을 써야 할까 생각해보니, 입력 받은 그 시점에 deque 혹은 stack에 넣고 폭발 문자열 수 만큼 뒤로 확인하면 시간 복잡도를 더 줄일 수 있다.

위의 알고리즘의 경우에는 find를 하기 위해 순차적으로 문자열을 탐색해야 한다.

2. 두 번째 풀이 : deque(or 스택)을 이용한 구현

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 

string str, bomb; 
deque<char> q;  

void input(){
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    str.reserve(1000004);//미리 할당  
    cin >> str >> bomb;
}

bool isBomb(string bomb, int bomblen, int pos){
    for(int i=0; i<=bomblen; i++){
        if( q[i] != bomb[ bomblen - i ]) return false;     
    }
    return true; 
}

void deleteBomb(int bomblen) {
    for (int i = 0; i <= bomblen; i++) {
        q.pop_front();
    }
}


void printQueue(){
    reverse(q.begin(), q.end());  
    while(!q.empty()){
        cout << q.front(); 
        q.pop_front();
    }
}

////  queue를 이용한 풀이 
void solve(){
    int bomblen = bomb.length() - 1; 
    //1. string 전체 순회 
    for(int i=0; i<str.length(); i++){//O(N*B)
        q.push_front(str[i]); 
        //2. 마지막 입력값이 bomb의 마지막 값과 같은지 체크 
        if(q.front() == bomb[bomblen]){
            //3. bomb의 마지막 값과 같다면 해당 위치부터 뒤로 bomb의 값과 전부 같은지 체크 
            if( isBomb(bomb, bomblen, i) ) deleteBomb( bomblen ); //같을 경우 bomb에 해당하는 문자열 제거 
        }
    }
    if(q.empty()) cout << "FRULA";
    else printQueue(); 
}    


int main() {
    input(); 
    solve();
    return 0;
}