스택 응용, 백준 9935: 문자열 폭발

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    stack<char> stack;
    string str, bomb;
    cin >> str >> bomb;
    
    int strSize = str.size();
    int bombSize = bomb.size();
    
    char bombEnd = bomb[bombSize - 1];
    
    for (int i = 0; i < strSize; i++) {
        char c = str[i];
        stack.push(c);
        
        if ( c == bombEnd ) {
            if( stack.size() < bombSize ) continue;
            
            string tempString = "";
            
            for (int j = 0; j < bombSize; j++) {
                tempString += stack.top();
                stack.pop();
            }
            reverse(tempString.begin(), tempString.end());
            
            if ( tempString.compare( bomb ) != 0 ) {
                for (int j = 0; j < bombSize; j++) {
                    stack.push( tempString[j] );
                }
            }
        }
    }
    
    int length = stack.size();
    if (stack.size() > 0) {
        string tempString = "";
        
        for (int i = 0; i < length; i++) {
            tempString += stack.top();
            stack.pop();
        }
        
        reverse(tempString.begin(), tempString.end());
        
        cout << tempString;
    }
    else {
        cout << "FRULA";
    }
    
    return 0;
}

 

문자열과 폭발 문자열을 받으면, 문자열에서 폭발 문자열을 완전히 없애는 문제입니다.

 

폭발 문자열의 크기를 알아두고,

폭발 문자열의 마지막 문자가 입력되면 스택에서 폭발 문자열 크기만큼 뽑아 문자열을 만들고,

만든 문자열과 폭발 문자열이 일치하면 제거하는 방식입니다.

 

이렇게하면 폭발 문자열을 제거한 다음, 제거한 문자열 이전 문자열과 이후 문자열이 합쳐져

새로운 폭발 문자열이 생기는 경우에도 바로바로 제거할 수 있습니다.

 

계속 반복돌려서 제거하는 건 해보진 않았는데 아마 시간 초과가 날 것입니다.