[백준/중상] 9935번 문자열 폭발 문제(스택+문자열 처리)

간단한 문제일 줄 알았으나, 은근 어려웠던 문제

우선 딱 봤을때 떠오르는 방법은 틀린 방법일 확률이 높은 문제이다.

왜냐하면 제한시간이 1초인데 문자열의 길이는 백만 까지 가능하다. 보통 비교연산을 1억번 정도 하는데 1초정도가 걸린다고 한다.

그런데 만약 빅오가 엔제곱인 알고리즘으로 이문제를 푼다면 백만곱하기 백만 이기때문에 1초로는 어림도 없다.

그래서 처음에 시간초과가 떴었다.

이 문제는 빅오가 엔인 알고리즘으로 풀어야만 문제를 풀 수 있다.

즉 문자열을 검사해 가면서 동시에 문자열을 바꿔야만 하기때문에 조금 까다로운 문제이다.

풀이방법

->

문자열을 검색해가면서 C4중 4를 만날때까지 검색을 한다.

현재 검색한 문자가 4가 아니라면 스택(배열로 표현됨)에 그 숫자를 넣는다.

4를 만났다면 거꾸로 내려가면서 방금전 지나쳐온것이 C 였는지를 확인한다.

즉 C4를 문자열에서 찾아낸다.

만약 C4를 찾아냈다면 C4 중 C에 해당하는 인덱스부터 새로 스택에 쌓는다. (숫자를 덮어씌운다는 의미)

전체코드

#include <iostream>
#include <string>
using namespace std;
 
char result[1000001];
int main()
{
    string str,bomb;
    cin>>str>>bomb; //str을 result에 bomb를 뺀 나머지 문자열을 넣을것이다.
    int index=0; //넣어야 하는 인덱스
    for(int i=0; i<str.size(); i++)
    {
        result[index++] = str[i];
        int j=(int)bomb.size();
        if(str[i] == bomb[--j]) //c4중 4부터 비교를 시작한다.
        {
            bool check = false;
            int size = index-(int)bomb.length();
            for(int k=index-1; k>=size; k--)
            {
                if(result[k] == bomb[j--])
                {
                    check = true;
                }
                else
                {
                    check = false;
                    break;
                }
            }
            
            if(check) index -= bomb.size();
        }
        
        
    }
    if(index==0)
        cout<<"FRULA"<<endl;
    else
    {
        for(int i=0; i<index; i++)
            cout<<result[i];
        cout<<endl;
    }
    
    
    return 0;
}