[C++] 백준 - 9935번 문제

9935번: 문자열 폭발 (acmicpc.net)

9935번: 문자열 폭발

 

9935번 : 문자열 폭발

---

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

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

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

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

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

 

입력

---

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

 

 

출력

---

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

 

 

 

---

 

생각해 볼 점

---

스택을 이용해서 풀 수 있습니다.

 

입력 문자열의 0번 인덱스부터 끝까지 한글자 씩 조사하면서 다음을 수행합니다.

 

1. 폭파 문자열[0]을 발견하면 스택에 숫자 0을 담습니다.

 

2. 폭파 문자열[스택의 Top()]이 현재 조사중인 문자와 다르면 스택을 비웁니다.

 

3. 스택의 top()의 숫자를 1 증가시킵니다.

 

4. 스택의 Top()의 크기가 폭파 문자열의 크기와 같아지면 문자열 폭파를 진행합니다.

 

 

문자열 폭파 : 스택을 pop()하고, 기존 문자열에서 폭파 문자열을 제거합니다.

 

 

 

코드

---

#include<iostream>
#include <stack>
using namespace std;
int main()
{
    char str[1000001];
    char bomb_str[37];
    scanf("%s", str);
    scanf("%s", bomb_str);
    int bomb_str_size = 0;
    for(; bomb_str[bomb_str_size]; bomb_str_size++)
        continue;

    int write_index = 0;
    stack<int> st;
    for(int i = 0; str[i]; i++)
    {
        str[write_index] = str[i];
        write_index++;
        if(str[i] == bomb_str[0])
            st.push({0});
        if(st.empty())
            continue;

        //폭파스택 비우기
        if(str[i] != bomb_str[st.top()])
        {
            st = stack<int>();
            continue;
        }
        st.top()++;

        //폭파
        if(st.top() == bomb_str_size)
        {
            write_index -= bomb_str_size;
            st.pop();
        }       
    }
    if(write_index == 0)
    {
        printf("FRULA");
        return 0;
    }
    
    str[write_index] = '\0';
    printf("%s", str);
    return 0;
}

 

그 외

---