[백준 C++] 9935번 문자열 폭발

9935번:

문제 요약

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

사용 알고리즘

스택

입출력

• 입력: 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.
• 출력: 첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다. ``` 예제1

입력 mirkovC4nizCC44 C4 출력 mirkovniz

## 풀이
스택을 활용하여 폭발 문자열과 앞부분이 일치하는것을 스택에 추가한다. 폭발문자열이 완전히 나오지 않았는데 새로운 폭발 문자열의 앞부분이 나오면 스택에 push한다. 만약 폭발문자열이 모두 완성되면 pop해버리고 중간에 일치하지 않는 문자열이 나온다면 스택에 있는 것을 모두 불일치한것으로 판단하고 출력할 문자열에 추가한다.

## 어려웠던 점
처음에 스택의 자료를 string 으로 잡고 풀었는데 시간초과가 났다. 너무 쉽다고 생각하긴 했다. 문자열이 불일치할때 스택에 있는 문자열을 일일이 꺼내와 출력할 문자열에 앞부분에 추가하는게 시간초과의 원인이라 생각하고 구조를 바꿨다. stack에 추가하는 대신 그냥 string에 뒤에 붙였고 stack으로는 int를 잡아 지금까지 일치한 문자열의 개수를 관리 하였다. 만약 이개수가 폭발문자열의 개수와 같으면 string에서 그만큼 지우면 되고 불일치하면 그냥 출력할곳에 string을 추가하면 된다.

## 배운 점 / 느낀 점
string을 더하고 계산하는게 상당히 느리다는 것을 알게 되었다. 중간에 if문의 순서와 폭발문자열이 한자리일경우를 고려하지 않아 좀 틀렸었는데 차분히 모든 경우를 생각해봐야겠다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

string s;
string t;
string r;

string stk;
stack<int> lk;
int l;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> s >>t;
    r = "";
    stk = "";
    int tn = t.length();
    lk = stack<int>();
    for(char c : s){
        if(!stk.empty() && c == t[lk.top()]){
            stk += c;
            lk.top() += 1;
            if(lk.top() == tn){
                lk.pop();
                stk.erase(stk.size()-tn);
            }
        }
        else if(c == t[0]){
            stk += c;
            lk.push(1);
            
            if(lk.top() == tn){
                lk.pop();
                stk.erase(stk.size()-tn);
            }
        }
        else{
            r += stk;
            r += c;
            lk = stack<int>();
            stk = "";
        }
    }
    r += stk;
    if(r == ""){
        cout << "FRULA";
    }
    else{
        cout << r;
    }

    return 0;
}