[백준] 9935 : 문자열 폭발

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

9935번: 문자열 폭발

---

• 폭발 문자열이 ABC 일 경우, AAABCBCBC 처럼 연속적인 폭발이 일어나는 경우들이 있다.
• 위의 경우, 가장 마지막에 나온 ABC 가 폭발하지 않으면 나머지 문자들도 처리될 수 없다.
• 폭발 문자열에는 중복되는 문자가 없기 때문에, 스택에 문자들을 차례대로 담다가 폭발문자열의 맨 마지막 문자 C 가 나오게 될 경우 최근 문자를 검사해서 ABC 라면 스택에서 뺴준다.
• 이런 식으로 처리를 하게 된다면, 연쇄적인 폭발도 스택에 남아있는 값들을 확인함으로써 처리된다.
• 스택의 최근 S(폭발문자열의 길이) 개 원소에 직접 접근이 가능해야 하므로, 스택 대신 문자열을 이용한다.

---

#include <iostream>
#include <stack>

using namespace std;

int idx;
string line, target, answer;                                                // 스택을 사용하지만, 최근 sz 만큼 랜덤액세스가 가능해야 해서 문자열로 함

int main(void)
{
    cin >> line;
    cin >> target;
    int sz = target.size();

    for(int i = 0 ; i < sz - 1 ; i++) answer.push_back(line[i]);            // 검사 조건 따로 넣기 싫어서 아예 시작을 sz-1 부터 함
    for(int i = sz - 1 ; i < line.size() ; i++)
    {
        answer.push_back(line[i]);                                          // 일단 스택(문자열)에 무조건 넣어줌

        if(line[i] == target[sz - 1])                                       // 그런데 만약 폭발문자열의 마지막 문자와 같을 경우에
        {
            for(idx = 0 ; idx < sz ; idx++)                                 // 스택의 최근 sz 만큼과 폭발문자열을 비교해서
            {
                if(answer[answer.size() - sz + idx] != target[idx]) break;
            }
            if(idx == sz)                                                   // 만약 폭발한다면 sz 만큼 스택에서 pop 해서 폭발 처리
            {
                for(int n = 0 ; n < sz ; n++) answer.pop_back();
            }                                                               // 폭발 안한다면, 스택 그대로 유지하면서 다음 끝문자 나올때까지 반복
        }
    }

    cout << (answer.size() ? answer : "FRULA") << endl;
}