백준 9935 문자열 폭발 c++ [컴공과고씨]

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

9935번: 문자열 폭발

 

문제 간단 정리

문자열이 2개 주어짐

하나는 전체 문자열 다른 하나는 폭발 문자열.

전체 문자열 안에 폭발 문자열이 있으면 그 폭발 문자열이 폭발하여 없어짐.

모든 폭발 문자열이 없어지고 난 후 전체 문자열에 남아 있는 문자열 구하라.

 

해결 방법

최대한 반복을 적게 해야지 시간 초과가 나지 않는다.

즉, 그냥 무작정 한 개씩 비교하다 폭발이 일어나고 다시 앞에서 비교하면 당연히 시간 초과가 난다.

전체 문자열 : qwd012301230123444klsmvk

폭발 문자열 : 01234

라고 했을 때 01234가 나오고 폭발한 다음 그 전에 있던 0123과 4가 합쳐지면 폭발이 연쇄적으로

일어난다. 이것을 효율적으로 처리해주어야 된다.

 

그래서 나는 전체 문자열을 하나씩 다른 문자열에 넣어주면서 이 문자열의 길이가 폭발 문자열의 길이가 같거나

커지면 문자열의 뒤에서 폭발 문자열 길이 만큼을 폭발 문자열과 비교해 같으면 폭발 시키고

아니면 문자열을 추가시키는 식으로 간단히 구현해 주었다.

 

예를 들면,

전체 문자열 : qwd012301230123444klsmvk

폭발 문자열 : 01234

임시 문자열을 t라고 하면

t="";

t="q", t="w" ... t="qwd01"이 되면 뒤에서 부터 5개 문자를 비교하여 폭발 문자열과 같은지 확인.

다르기 때문에 계속 추가 그러다가 t="qwd0123012301234" 가 되어서 폭발 문자열과 같아지면 폭발.

그럼 t="qwd012301230123"이 되고 다시 뒤에 문자 추가 하면 t="qwd0123012301234"가 되어서

폭발 ... 이렇게 반복이되다 보면 폭발 문자열이 모두 폭발하게 된다.

 

코드를 보면 더욱 쉽게 이해가 가능하다.

#include<iostream>
#include<string.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string a; // 전체 문자열 변수
    string b; // 폭발 문자열 변수
    string t = ""; // 임시 문자열 
    cin >> a >> b;
    int a_len = a.length(); // 전체 문자열 길이
    int b_len = b.length(); // 폭발 문자열 길이
    for (int i = 0; i < a.length(); i++)
    {
        t += a[i]; // 문자 추가
        if(t.length()>=b_len){ // 임시 문자 길이가 폭발 문자열 보다 크거나 같을 때
            bool flag = true; // 폭발 문자열 있는지 확인하는 flag
            for (int j = 0; j < b_len; j++){ 
                if(t[t.length()-b_len+j] != b[j]){
                    flag = false;
                    break;
                } // t뒤에서 폭발 문자열 길이만큼 비교
            }
 
            if(flag) // 폭발 문자열일 경우 삭제 
                t.erase(t.end() - b_len, t.end());
        }
    }
        if (t.empty()) // 남아 있는 문자열이 없는 경우
            cout << "FRULA" << '\n';
        else
            cout << t << '\n';
    return 0;
}