[BaekJoon][9935] 문자열 폭발

BAEKJOON ONLINE JUDGE

9935번 문자열 폭발

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

풀이

입력 받은 문자열을 하나씩 검사하면서 폭발 문자열과 일치할 경우 stack에 넣고 비교

괄호 비교 문자와 비슷하게 풀면 된다.

#include <stdio.h>
#include <stack>
#include <string.h>
using namespace std;
 
char input[1000010];
char boom[40];
int inputsize, boomsize;
stack<pair<int, int>> stc;
 
void case1()
{
    int flag = 0;
    for (int i = 0; i < inputsize; i++) {
        if (input[i] != boom[0]) {
            flag = 1;
            printf("%c", input[i]);
        }
    }
    
    if (flag)    printf("\n");
    else        printf("FRULA\n");
}
 
void case2()
{
    int flag = 0;
 
    for (int i = 0; i < inputsize; i++) {
        if (input[i] == boom[0]) {        // 같으면 stack에 넣기
            stc.push(make_pair(i, 0));
        }
        else {        // 일단 boom의 0번째랑 달라
            if (stc.empty())        continue;        
                // 스택이 비어있으면 버림
            
            if (input[i] == boom[stc.top().second + 1]) {    
                // boom의 다음 녀석이랑 같으면 stack에 넣기
                stc.push(make_pair(i, stc.top().second + 1));
 
                if (stc.top().second + 1 == boomsize) {    
                    // boom이 완성되면 그만큼 pop
                    for (int j = 0; j < boomsize; j++) {
                        input[stc.top().first] = '-';
                        stc.pop();
                    }
                }
            }
            else {
                while (!stc.empty()) {
                    stc.pop();
                }
            }
        }
    }
 
    for (int i = 0; i < inputsize; i++) {
        if (input[i] != '-') {
            flag = 1;
            printf("%c", input[i]);
        }
    }
    
    if (flag)    printf("\n");
    else        printf("FRULA\n");
}
 
int main()
{
    int i;
 
    scanf("%s\n%s", input, boom);
 
    inputsize = strlen(input);
    boomsize = strlen(boom);
 
    if (boomsize == 1)        case1();
    else                        case2();
 
    return 0;
}