[Python] 백준 / gold / 9935 : 문자열 폭발

문제 링크 : https://www.acmicpc.net/problem/9935

문자열 + 스택을 활용한 문제였다. 요새 KMP, Rabin Carp 알고리즘에 대해 공부하다 보니 괜히 고급 알고리즘을 사용해야 하는 것 아닌가 생각이 들었던 것 같다.
문자열의 길이가 최대 1,000,000 이었기 때문에 그런 생각이 든 것 같기도 하다. 항상 느끼는 거지만, 나는 문제를 스스로 어렵게 만드는 경향이 있다. 기본에 충실해서 stack 자료구조를 활용해서 풀면 시간복잡도 통과할 수 있는 문제였다. 문제가 막힐 때, 기본 자료구조와 알고리즘을 떠올려 보는 습관을 잊지 않아야겠다..

파이썬 정답 코드

import sys
given = sys.stdin.readline().strip()
bomb = sys.stdin.readline().strip()

stack = []

i = 0
while i < len(given):
    stack += given[i]
    if len(stack) >= len(bomb) and "".join(stack[-len(bomb):]) == bomb:
       for _ in range(len(bomb)): stack.pop()
    i+=1

if not stack: print("FRULA")
else:
    print("".join(stack))