[백준] 9935번 문자열 폭발

문제

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

풀이과정

처음에는 문자열을 처음부터 ans라는 문자열 변수에 하나씩 넣어가며 문자열 끝부터 폭발문자열의 길이만큼의 chk_str을 만들어 폭발문자열과 비교하고 같으면 substr을 통해 ans 문자열에서 폭발문자열을 제거하는 식으로 해결하고자 했다. 하지만 제출결과는 시간 초과가 났다. 그 이유를 살펴보니 입력되는 문자열의 최대길이는 백만이고 시간제한이 1초이므로 시간복잡도 O(N) 정도로 해결해야하는 문제였다.

그래서 다시 생각해서 새로운 알고리즘을 생각했다.

1. 입력 문자열을 순차적으로 ans 문자열 변수에 넣는다.
2. 만약 넣는 문자가 폭발문자열의 끝 문자와 같다면
3. 폭발문자열의 길이만큼 ans 문자열을 검사한다
4. ans의 끝 쪽이 폭발문자열이면 폭발문자열의 길이만큼 pop() 시킨다.

위와 같은 과정을 vector와 string으로 구현을 해봤는데 string이 속도가 더 빨랐다. 원래는 스택을 사용하는 문제지만 굳이 스택을 쓰지않고 문자열만 사용해서 처리할 수 있어서 문자열을 사용했다.

소스코드

#include <iostream>
#include <string>

using namespace std;

string input_str, bomb,ans;
bool chk_fire;

int main()
{
    cin.sync_with_stdio(false);

    cin >> input_str >> bomb;

    int input_len = input_str.length();
    int bomb_len = bomb.length();

    for (int i = 0; i < input_len; i++)
    {
        ans += input_str[i];
        // 폭발문자열의 끝 문자와 일치할 경우 비교
        if (input_str[i] == bomb[bomb_len - 1] && i >= bomb_len-1)
        {
            chk_fire = true;
            // ans에 들어간 최근 문자열을 bomb_len만큼 비교하여 폭발문자열과 일치하는지 비교한다.
            for (int j = 1; j < bomb_len; j++)
            {
                // 폭발문자열과 다른 문자가 있을 경우
                if (ans[ans.size()-1 - j] != bomb[bomb_len-1 - j])
                    chk_fire = false;
            }

            // 폭발문자열과 일치하면 폭발문자열의 길이만큼 ans의 끝을 pop() 시켜준다
            if (chk_fire)
            {
                for (int k = 0; k < bomb_len; k++)
                    ans.pop_back();
            }
        }
    }

    if (!ans.empty())
    {
        cout << ans;
    }
    else
        cout << "FRULA";

    return 0;
}