[백준][C++] 9935: 문자열 폭발

문제

 

풀이

• 전체 입력받은 문자열을 처음부터 끝까지 폭발 문자열이 없을 때까지 검색을 반복하면 시간초과가 된다.
• answer 문자열을 따로 두어, 전체 문자열의 0번 인덱스부터 검사하여 answer문자열이 폭발 문자열의 길이보다 길어진다면 answer의 끝 부분을 폭발 문자열과 비교한다. 
• answer의 끝 부분이 폭발 문자열이라면 삭제한다. 

코드

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    string bomb;

    cin >> s >> bomb;

    string answer;

    int bomb_len = bomb.length();

    for (int i = 0; i < s.length(); ++i)
    {
        answer.push_back(s[i]);

        // 현재까지 채워넣은 answer의 길이가 폭탄 길이보다 클 경우만 비교
        if (answer.length() >= bomb_len)
        {
            // answer의 끝 부분이 폭탄과 같다면 폭발
            bool flag = true;
            for (int j = 0; j < bomb.length(); ++j)
            {
                if (answer[answer.length() - bomb_len + j] != bomb[j])
                {
                    flag = false;
                }
            }

            // 폭탄 부분 삭제
            if (flag)
            {
                answer.erase(answer.end() - bomb_len, answer.end());
            }
        }
    }

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

    return 0;
}