[백준 9935] 문자열 폭발

0. 제목

• 백준 9935 문자열 폭발
• BOJ 9935 문자열 폭발
• C++ 9935 문자열 폭발

---

1. 문제

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

---

2. 풀이

• 입력 문자열의 길이가 1000000까지 될 수 있기 때문에 O(N)으로 탐색을 해야 시간 내에 통과할 수 있다.
• 처음부터 탐색하는 것을 반복하면 시간이 오래 걸리기 때문에 처음부터 비교해가면서 즉각 제거 하는 방식으로 풀어야 한다.
• 예를 들어보겠다. 문자열 abcde가 주어지고 폭발 문자열로 cd가 주어졌다고 하자. 문자열이 폭발 문자열의 마지막 문자인 d와 같을 때 역으로 비교해주어야 한다.
• result라는 배열은 폭발하지 않는 문자열을 담는 배열이다.
• 문자열에서 d가 나오는 순간 문자열의 d 전에 나오는 문자가 c인지 확인 해주어야 한다.
• 만약 맞다면 check를 true로 갱신해준다. 
• 틀리다면 check는 false이고 역으로 비교하는 과정을 멈춘다.
• 역으로 비교하는 과정이 끝나고 나서 check의 값이 true이면 result의 현재 index에서 폭발 문자열의 길이만큼 빼준다. 그렇게 되면 폭발 문자열을 제외한 후부터 다시 result배열에 문자열이 담길 것이다.
• 폭발 문자열이 다 폭발하고 난 후 result의 index가 0이라면 FRULA를 출력해주고 아니라면 result배열의 원소들을 차례로 출력해준다.

---

3. 코드

#include <iostream>
#include <string>
using namespace std;
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    string str;
    string bomb;
    char result[1000001];
    
    cin >> str >> bomb;
    int len1 = (int)str.length();
    int len2 = (int)bomb.length();
    int index = 0;
    for(int idx1 = 0; idx1 < len1; idx1++){
        result[index++] = str[idx1];
        int bombSize = len2;
        if(str[idx1] == bomb[--bombSize]){
            bool check = false;
            int size = index - len2;
            for(int j = index - 1; j >= size; j--){
                if(result[j] == bomb[bombSize--]){
                    check = true;
                }else{
                    check = false;
                    break;
                }
            }
            if(check == true)
                index -= bomb.length();
        }
    }
 
    if(index == 0){
        cout << "FRULA" << '\n';
    }
    else{
        for(int i = 0; i < index; i++)
            cout << result[i];
        cout << '\n';
    }
    
    return 0;
}