[백준 9935] 문자열 폭발

 스택 입문으로 풀기에는 쉬운 문제는 아니다.

 보자마자, 떠오르는 방법으로 구현을 해봤지만

 보기 좋게 틀린 문제이다.

또한 질문게시판에서 반례를 찾아봤지만,

문제의 조건에 맞지 않는 반례 때문에 헤매기도 하였다.

( 조건 : 폭발 문자열에서 같은 문자는 2번 이상 나올 수 없습니다)

 

 stack<pair<int, int> > st 을 사용하여

first에는 문자열의 해당하는 위치

second에는 폭발 문자열에 해당하는 인덱스를 삽입하며 진행한다.

기존 문자열 : mirkovC4nizCC44

폭발 문자열 : C4



1. if(a[i] == b[0])

// m i r k o v ...


이때 C에서 (a[6] == b[0]) 이기 때문에 

st.push(make_pair( i, 0 )을 시켜준다.


** 폭발 문자열의 첫번째 문자는 매번 검사해줘야 한다 **

( 폭발 이후 합쳐지고 폭발이 가능할 수 있기 때문에)


2. st.top().second + 1

( 진행한 폭발 문자열 인덱스 + 1)을 검사하여


차례대로 이어간 이후에




3. if((st.top().second + 1) == b.size() - 1)

(폭발 문자열 조건 만족하면)




4. erased[st.top().first] = true 를 만들어주고

st.pop을 해주면 된다 ( 폭발 문자열 갯수 만큼 )

출력은 erased와 a(기존 문자열)을 비교하여 처리해주면 된다.


이때 문제에서 출력 값이 없을 시, FRULA를 출력하라고 했기 때문에

적절히 만족시켜주면 된다.

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

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

mirkovC4nizCC44
C4

예제 출력 1

mirkovniz

예제 입력 2

12ab112ab2ab
12ab

예제 출력 2

FRULA

소스코드

#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
 
using namespace std;
 
#define MAX 1000001
char str[MAX];            // 기존 문자열 
bool erased[MAX];        // 지워야 하는 문자열 
char boom[100];            // boom! 폭발시켜야 하는 문자열 
bool check;            // 남는 것이 하나도 없는지 check 
 
int main(){
    cin >> str;
    cin >> boom;
    int n = strlen(str);
    int m = strlen(boom);
    
    if(m == 1){                    // 폭발시켜야 하는 문자열 길이가 1이면 
        for(int i = 0; i < n; i++){        // for문으로 빠르게 처리 
            if(str[i] == boom[0]){
                erased[i] = true;
            }
        }
    }
    else{
        stack<pair<int, int> > st;        // stack의 first는 a의 인덱스, second는 해당 문자 
        pair<int, int> p;
        for(int i = 0; i < n; i++){
            if(str[i] == boom[0]){
                st.push(make_pair(i,0));
            }
            else{
                if(!st.empty()){
                    p = st.top();                            // p는 지울 수 있는 후보 문자 
                    if(str[i] == boom[p.second+1]){                    // 지워야하는 다음 문자를 찾은 경우 
                        st.push(make_pair(i,p.second+1));
                        if(p.second+1 == m-1){                    // 문자열을 모두 찾은 경우 
                            for(int k = 0; k < m; k++){            // 지워준다 
                                p = st.top();
                                erased[p.first] = true;
                                st.pop();
                            }
                        }
                    }
                    else{                                // 시작 문자도 아니고 마지막 문자도 아니기 때문에
                        while(!st.empty())                             
                            st.pop();
                    }
                }
            }
        }
    }
    
    for(int i = 0; i < n; i++){
        if(erased[i])
            continue;
        check = true; 
        cout << str[i];
    }
    if(!check)
        cout << "FRULA";
    
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.