BOJ_9935(문자열폭발)

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

접근 방식

1. 문자열의 길이는 1보다 크고, 1,000,000보다 작거나 같다. 즉 이중 loop를 사용할 경우 바로 시간 초과가 걸린다.
2. 이중 loop를 사용하지 않고 문제를 해결하기 위해서, 투포인터, 이분탐색, DP와 스택 등을 생각할 수 있다.
3. "폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다." 와 같이 어떠한 규칙에 의한 변화가 연속으로 일어날 수 있는 경우, 대게 스택을 사용할 수 있었다.

구현

알고리즘 요약:
문자 하나씩 스택에 추가한다 →
만약 추가할 문자가 폭발 문자열의 마지막 문자와 일치 할 경우 →
스택에서 폭발 문자열의 길이만큼 문자를 꺼내 비교한다

주의:
스택이 비어있을 때, break 처리를 하지 않으면 시간초과가 발생한다.
폭발 문자열의 길이는 길어봤자 36이기 때문에 따로 처리를 안해줬었는데, 문자열의 길이가 최대 1,000,000 임을 고려했을 때 최악이 경우를 대비해 해주는 게 옳다.

import sys
input = sys.stdin.readline

# 입력
word = input().rstrip()
target = input().rstrip()

# 반복
stk = []
for ch in word:
    if ch != target[-1]:
        stk.append(ch)
    else:
        tmp = ch
        for i in range(len(target) - 1):
            if stk:
                tmp += stk.pop()
            else:
                break
        tmp = tmp[::-1]
        if tmp != target:
            stk += tmp

ans = "".join(stk)
if ans == "":
    print("FRULA")
else:
    print(ans)