Baekjoon 9935번 문자열 폭팔

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string S, P; 
    cin >> S >> P;
    string s;
    for(int i = 0; i < S.size(); i++){
        s.push_back(S[i]);
        if(s.size() >= P.size()){
            bool isValid = true;
            for(int j = 0; j < P.size(); j++){
                if(s[s.size()-P.size()+j] != P[j]){
                    isValid = false;
                    break;
                }
            }
            if(isValid){
                for(int j = 0; j < P.size(); j++){
                    s.pop_back();
                }
            }
        }
    }
    if(s.empty()) cout << "FRULA";
    else cout << s;
    return 0;
}

문자열 전체에서 모든 폭팔 문자열을 찾아 동시에 제거해나가는 시간초과 방법밖에 떠오르지 않아 문제 분류를 보았다.

스택 개념을 이용해 문자열이 들어올 때 마다 폭팔 문자열과 일치하는지를 조사하면 복잡도가 1,000,000 * 36 으로 시간안에 해결할 수 있다.