[BOJ/백준][Gold4] 9935 : 문자열 폭발 (C++)

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

[난이도] Gold4

[유형] 스택

 

[풀이]

A를 전체 문자열 B를 폭발 문자열이라고 했을 때
A를 i: 0~N-1까지 순회하면서 i와 A[i]의 B에서의 index를 스택에 저장
방식으로 답을 구한다.

 

#include <stack>
#include <iostream>
#include <string>
using namespace std;
bool erase[1000001];
string a,b;
stack<pair<int,int>> s;
int main(){
    cin >> a >> b;
    if(b.size()==1){
        for(int i=0;i<a.size();i++) if(a[i]==b[0]) erase[i] = 1;
    }else{
        for(int i=0;i<a.size();i++){
            if(!s.empty() && b[s.top().second+1]==a[i]){
                s.push({i,s.top().second+1});
                if(s.top().second==b.size()-1) {
                    int sz = b.size();
                    while(sz--) {
                        erase[s.top().first] = 1;
                        s.pop();
                    }
                }
            }
            else if(a[i]==b[0]) s.push({i,0});   
            else while(!s.empty()) s.pop();
        }
    }
    string ret;
    for(int i=0;i<a.size();i++) if(!erase[i]) ret += a[i];
    if(ret=="") puts("FRULA"); 
    else cout << ret;
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/9935.cpp