백준 9935 - 문자열 폭발

문제

 

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

9935번: 문자열 폭발

 

 

풀이

 

스택을 이용해서 폭발 문자열과 관련된 인덱스를 저장하고 erase 배열에는 폭발할 문자열의 인덱스를 체크한다. 문자열과 폭발 문자열을 하나씩 비교해가면서 같으면 스택에 문자열의 인덱스와 비교 길이(match_len)을 저장한다. 다르다면 스택을 비워주고 비교길이(match_len)을 0으로 한다. 비교 길이가 폭발 문자열의 길이와 같으면 폭발 문자열이 들어가 있는 것이므로 erase 배열에 스택에 들어있는 인덱스들을 체크해주면 된다. 이 방법은 문자열 a=CC44가 있고 폭발 문자열이 b=C4일 때 문제가 된다. 가운데 C4만 제거가 되기 때문이다. 그래서 a[i] == b[0]일 때, 예외적으로 비교 길이(match_len)를 1로 지정하고 스택에 저장을 한다. 그러면 문자열 a에서 가운데 C4를 스택에서 제거한 후에도 스택에는 C(a[0])가 남아있고 같이 저장한 match_len도 저장되어 있다. 그러면 스택에 저장되어 있는 정보를 가지고 이어서 뒤에 폭발 문자열을 비교할 수 있다.

 

 

코드

 

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
string a, b;
bool erase[1000000];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> a >> b;
 
    if (b.size() == 1)
    {
        for (int i=0; i<a.size(); i++)
        {
            if (a[i] == b[0]) erase[i] = true;
        }
    }
    else
    {
        stack<pair<int, int>> st;
        int match_len = 0;
        for (int i=0; i<a.size(); i++)
        {
            if (a[i] == b[match_len])
            {
                match_len++;
                st.push({i, match_len});
            }
            else if (a[i] == b[0])
            {
                match_len = 1;
                st.push({i, match_len});
            }
            else
            {
                match_len = 0;
                while (!st.empty()) st.pop();
            }
            
            if (match_len == b.size())
            {
                for (int j=0; j<match_len; j++)
                {
                    auto top = st.top();
                    st.pop();
                    erase[top.first] = true;
                }
 
                if (!st.empty()) match_len = st.top().second;
            }
        }
    }
 
    bool FRULA = true;
 
    for (int i=0; i<a.size(); i++)
    {
        if (!erase[i])
        {
            cout << a[i];
            FRULA = false;
        }
    }
 
    if (FRULA) cout << "FRULA";
 
    return 0;
}