9935 문자열 폭발

9935 문자열 폭발 (c++)

문제

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

접근 방식

스택, 문자열
1차시도

1. str.find()를 이용해서 지워야할 target의 시작위치를 찾고, 지우기를 반복 (시간초과)

2차시도

1. 직접 find 함수를 만들어서 erase 대신 str을 target의 전 문자열과 후 문자열의 합으로 갱신 (시간초과)

3차시도

1. 못풀겠어서 알고리즘 분류를 봄, 스택이 적혀있었음
2. 생각해보니 trigger를 target의 끝문자로 잡고 trigger가 발견될때마다 스택에서 꺼내서 체크하면 될 것 같았음
3. 일단 trigger를 target의 마지막 char로 설정
4. 문자열을 순회하다 trigger을 발견하면 아래의 과정을 실행
   1. target의 길이와 현재 stack의 길이를 비교한다.
      1. stack의 길이가 더 짧으면 target이 아니므로 cotinue;
      2. stack의 길이가 target의 길이보다 길거나 같으면 아래의 과정을 진행
   2. target의 길이만큼 stack에서 꺼낸다.
   3. stack은 LIFO이므로 reverse를 해준다.
   4. 꺼낸 문자열과 target이 같으면 그대로 진행
   5. 다르면 다시 stack에 집어넣어 주기

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

string str, target;
stack<char> stk;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> str >> target;

    int strLength = str.length();
    int targetLength = target.length();

    for (int i = 0; i < strLength; ++i)
    {
        if (str[i] == target[targetLength - 1])
        {
            if (stk.size() >= targetLength - 1)
            {
                // 검사
                string temp = "";
                for (int j = 0; j < targetLength - 1; ++j)
                {
                    temp += stk.top(); stk.pop();
                }
                reverse(temp.begin(), temp.end());
                temp += str[i];

                if (temp == target)
                {
                    continue;
                }
                else
                {
                    for (int j = 0; j < targetLength - 1; ++j)
                    {
                        stk.push(temp[j]);
                    }
                }
            }
        }

        stk.push(str[i]);
    }

    string answer = "";
    while (!stk.empty())
    {
        answer += stk.top(); stk.pop();
    }

    if (answer.length() == 0) cout << "FRULA\n";
    else
    {
        reverse(answer.begin(), answer.end());
        cout << answer << '\n';
    }


    return 0;
}

다시 생각해 볼 점

1. ‘문자열이 안풀리면 세로로 세워보자’ 라는걸 항상 기억하자.