백준 - 9935번(스택)

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

9935번: 문자열 폭발

 

import sys

arr = list(str(sys.stdin.readline().rstrip()))
key = list(str(sys.stdin.readline().rstrip()))

stack = []

for i in arr:
    stack.append(i)
    if i == key[-1] and stack[-len(key):] == key:
        del stack[-len(key):]


if len(stack) == 0:
    print('FRULA')
else:
    ans = ''.join(stack)
    print(ans)

정신 나간 문제다. 코드 길이 대비 시간 투자 한 문제 1위다.
stack은 arr의 앞에서 부터 쌓아주고 key는 -1부터 봐주는 걸 떠올리지 못하면 절대 풀지 못한다.
(사실 절대는 아니고 다른 방법이 있겠지만 나는 모르겠다.)
왜 이걸 못떠올려서 헤매었을까... stack은 위로 쌓이는 구조다. 따라서 가장 앞에 본 것이 가장 밑에 깔린다.
그럼 가장 위에서 꺼낼 수 있는건 가장 마지막 원소 이므로 비교대상이 되는 key를 뒤에서부터 탐색해준다.
그렇지만 추천할 만한 문제다.