BOJ 9935번: 문자열 폭발

문제

문제 바로가기> BOJ 9935번: 문자열 폭발

9935번: 문자열 폭발

 

풀이

문자열을 폭발시킬 때는 LIFO, 남은 문자열을 합칠때는 FIFO 자료구조가 용이하기에 deque를 사용했다.

문자열 폭발시 LIFO 자료구조를 이용하여 시간을 단축시킬 수 있는데,

그 이유는 가장 최신 폭발 문자열 개수만 보고 판단할 수 있고, stack 덕분에 문자열의 순서가 유지되기 때문이다.

( + stack 같은 자료구조의 유용성을 알 수 있는 좋은 문제같아서, 한번 풀어보면 좋을 거 같다!! 추천! )

#include<iostream>
#include<deque>
using namespace std;

deque<char> s, tmp;
string str, bombstr;

void input(){
    cin >> str >> bombstr;
}

void solve(){
    for (int i = 0; i < str.size(); i++){
        s.push_back(str[i]);
        if(bombstr.size() <= s.size()){ // 폭발 문자열의 길이 요건 충족
            bool ismatch = true;
            for (int j = bombstr.size() - 1; j >= 0; j--){ // 가장 최신 bombstr.size()개를 비교하여 폭발 문자열인지 확인
                if(s.back() == bombstr[j]){
                    tmp.push_back(s.back()); // 폭발 문자열이 아닌 경우, 다시 메인 스택에 저장해주기위해 임시 저장
                    s.pop_back();
                }
                else{ // 폭발 문자열과 match되지 않는 경우
                    ismatch = false;
                    while (!tmp.empty()){ // 임시 스택에 저장해둔 폭발 문자열이 아닌 문자열을 다시 메인 스택에 옮겨줌
                        s.push_back(tmp.back());
                        tmp.pop_back();
                    }
                    break; // 더 이상 볼 필요 없음
                }
            }
            while (ismatch && !tmp.empty()) tmp.pop_back();  // 폭발 문자열을 저장해둔 임시 stack을 비워줌
        }
    }
}

void output(){
    string res = "";
    while (!s.empty()){
        res += s.front();
        s.pop_front();
    }
    res == "" ? cout << "FRULA" : cout << res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solve();
    output();
}