백준 9935번 - Python

백준 9935번 - 문자열 폭발

생각한 풀이

처음에는 find함수를 사용하여 문제를 풀었으나 시간초과가 발생하였다. find함수를 이용하여 문자열에서 폭발문자열을 계속 없애는 식으로 반복문을 돌렸었다. 그러나 이런식으로 풀면 새로운 문자열이 계속 생성되어 시간초과가 발생하였다.
그래서 스택을 이용해서 문자열을 쌓고 뒤에서부터 확인하도록 구현하였다.
1. 문자열만큼 반복문을 돌리며 문자열을 스택에 쌓는다.
2. 만약 스택의 뒤에서 부터 폭발 문자열의 길이만큼 슬라이싱해서 보았을때 폭발 문자열과 같다면 폭발 문자열의 길이만큼 스택에서 빼준다.
3. 스택이 비어있지 않다면 리스트를 문자열로 합쳐서 보여주고, 비어있다면 FRULA를 출력한다.

코드

import sys
string = sys.stdin.readline().strip()
boom = [*sys.stdin.readline().strip()]
stack = []

for i in string:
  stack += i
  if stack[-len(boom)::] == boom:
    for _ in range(len(boom)):
      stack.pop()
if stack: 
  print(''.join(stack))
else:
  print('FRULA')

결과