9935 문자열 폭발

#include <stdio.h>
#include <stack>
#include <utility>
#include <string.h>
 
using namespace std;
 
char arr[1000005] = { 0 };
char bomb[40] = { 0 };
stack<pair<char, int> > stk;
 
int main() {
    scanf("%s %s", &arr, &bomb);
 
    int len_arr = strlen(arr);
    int len_bomb = strlen(bomb);
 
    int idx = 0;
    for (int i = 0; i < len_arr; i++) {
        // 일치할경우
        if (arr[i] == bomb[idx]) {            
            stk.push(make_pair(arr[i], idx));
            idx += 1;
        
            if (idx == len_bomb) {
                for (int j = 0; j < len_bomb; j++)
                    stk.pop();
 
                // 1234123 & 1234 같은 경우를 막기 위함
                // 첫부분 1234 를 처리하고 나면, stk.top() 에서 에러가 나므로 별도 처리
                if (!stk.empty())
                    idx = stk.top().second + 1;
                else
                    idx = 0;
            }                
        }
        // 불일치할경우
        else {
            idx = 0;
 
            // 1231234 & 1234 같은 경우를 고려하기 위함
            // 두 번째 1 을 넣으려 할때, idx=0 으로 하고 넣어줘야 한다
            if (arr[i] != bomb[0])
                stk.push(make_pair(arr[i], -1));
            else
                stk.push(make_pair(arr[i], idx++));
        }
    }
    
    // 아무것도 남아있지 않을 경우
    if (stk.empty())
        printf("FRULA");
    // 남아있는 문자가 있을경우
    else {
        stack<char> tmp_stk;
 
        while (!stk.empty()) {
            char tmp_char = stk.top().first;
            stk.pop();
 
            tmp_stk.push(tmp_char);
        }
 
        while (!tmp_stk.empty()) {
            printf("%c", tmp_stk.top());
            tmp_stk.pop();
        }
    }
}

여러번 for 문을 돌려서 완전탐색을 했다가, 시간 초과가 나서 스텍을 이용했다

총 시간복잡도는 O(N) 정도가 되므로, 아주 효율적이다