[c/c++] 백준 9935

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

9935번: 문자열 폭발

접근 방식

처음엔 괄호가 옳바르게 쓰였는지 확인하는 문제처럼 접근했다.
하지만 괄호 문제와는 다르게 폭발 문자열이 괄호처럼 한쌍으로 이루어진게 아니었기 때문에 괄호처럼 푸는 것은 어려울 것이라 생각하고 다른 방법을 생각해보았다.

그 다음으로 생각해본건 stack에 한 글자씩 넣으며 문자열이 있는지 검사하는 방법을 생각했다.
하지만 완전 탐색을 하게 되면 시간 복잡도가 O(n^2)이 되는데 n<=1,000,000이므로 시간 초과가 나게 된다.

풀이 방법

입력을 한 글자씩 받게 되는데 한 글자를 받을 때 stack에서 생길 수 있는 폭발 문자열의 최대 개수는 1개이다.
그리고 입력이 폭발 문자열의 마지막 문자여야만 폭발 문자열이 생기게 된다.
즉 입력을 받은 곳이 아닌 엉뚱한 곳에서 폭발 문자열이 생기지 않는다는 말이다.
그래서 한 글자를 받았을 때 stack의 크기가 폭발 문자열의 크기보다 크다면 top에서 폭발 문자열의 크기만큼만 빼준 index부터만 검사하여 폭발 문자열이라면 그 크기만큼 pop해주면 폭발 문자열을 제거할 수 있다.
이렇게 하면 시간 복잡도가 O(nm)이 되는데 n<=1,000,000 m<=36이므로 시간 내에 돌아간다.

코드

#include<iostream>
#include<string>

using namespace std;

int main()
{
    string s,target;
    char sta[1000001];
    int top=0;
    cin>>s>>target;
    
    int s_len=s.length();
    int t_len=target.length();
    
    for(int i=0;i<s_len;i++){
        sta[top++]=s[i];
        if(top>=t_len){
            int flag=1;
            for(int j=0;j<t_len;j++){
                if(sta[j+top-t_len]!=target[j]) flag=0;
            }
            if(flag) top-=t_len;
        }
    }
    
    sta[top]='\0';
    
    if(!top) cout<<"FRULA";
    else cout<<sta;
    
    return 0;
}

배열이 아닌 vector로 구현하려고 했지만 vector로 하게 되면 문자열 길이만큼 pop해주어야해서 그냥 배열로 구현하여 top을 이용하여 index만 바꿔주는 식으로 구현했다. 하지만 이렇게 하면 stack에 top보다 큰 index에도 값이 존재할 수 있으므로 마지막에 '\0'을 넣어주어 문자열의 끝을 구분해주었다.