백준 9935 - 문자열 폭발

문제 설명

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

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

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 전체 문자열과 폭발 문자열이 주어질 때, 전체 문자열에 포함된 폭발 문자열은 폭발하여 없어진다.

예를 들어, 

mirkovC4nizCC44
C4

처음 나오는 C4가 없어져 mirkovnizCC44가 되고 이후 CC44가 중 빨간 부분이 없어져 mirkovnizC4가 되고 마지막 C4가 또 없어져 mirkovniz가 된다.

 

해당 문제는 예외가 많아 상당히 많이 시도했다.

풀이 방법은 전체 문자열을 순회하며 폭발 문자열을 순서대로 만들어 나가는 것이다.

폭발 문자열을 완성했다면 그대로 폭발하여 없어지게 한다.

만약, 폭발 문자열을 만들다 순서에 어긋나는 문자가 들어온다면 두 가지 분기로 갈린다.

• 폭발문자열의 시작 문자: 현재 만들던 폭발 문자열을 저장한 후 처음부터 다시 만든다.
• 이외의 문자: 현재까지 만든 폭발 문자열은 절대 폭발 문자열이 될 수 없으므로 정답에 더한다.

 

AABC
ABC

폭발 문자열을 만들다 A이후 다시 A가 나온다.

다시 시작 문자가 나왔기 때문에 폭발 문자열이 될 가능성이 존재한다.

따라서 이전 문자열인 A를 저장해 놓고 새로 만들어 나간다.

이후, ABC가 완성되면 폭발되어 없어지고 이전에 저장한 A만 남아 정답은 A가 된다.

 

이전 폭발 문자열을 저장하는 방법은 deque를 이용하는 것이 좋다.

폭발 문자열을 완성하면 이전에 만들던 폭발 문자열을 하나 꺼내 다시 만들어 가야 하기 때문에 LIFO인 stack의 성질이 필요하고 폭발 문자열을 만드는 게 불가능한 경우에는 먼저 만든 문자열들이 먼저 정답에 포함되어야 하기 때문에 FIFO인 queue의 성질이 필요하다.

따라서, 둘 다 지원하는 deque를 이용하는게 편하다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

string str, bomb;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> str >> bomb;

    deque<string> stack;
    string current;
    string ans;
    for (int i = 0; i < str.size(); i++)
    {
        char c = str[i];
        if (c == bomb[current.size()])
        {
            current += c;
        }
        else if (c == bomb[0])
        {
            //새로 시작
            stack.push_back(current);
            current = c;
        }
        else
        {
            while (!stack.empty())
            {
                ans += stack.front();
                stack.pop_front();
            }

            ans += (current + c);
            current = "";
        }

        if (current == bomb)
        {
            if (!stack.empty())
            {
                current = stack.back();
                stack.pop_back();
            }
            else
            {
                current = "";
            }
        }
    }

    while (!stack.empty())
    {
        ans += stack.front();
        stack.pop_front();
    }
    ans += current;

    if (ans == "") cout << "FRULA";
    else cout << ans;

    return 0;
}

---