백준 9935. 문자열 폭발 (Python)

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

풀이

stack을 이용해 해결하는 문제이다..!

S=input()
bomb=input()
while True:
    tmp_S=S.replace(bomb,'')
    if S==tmp_S:
        S=tmp_S
        break
    S=tmp_S
print('FRULA' if len(S)==0 else S)

처음엔 단순하게 폭탄문자열을 replace함수를 이용해 지워주는 방향으로 진행했는데 당연하게도 시간초과가 뜬다
ex)
aaaaaaaaaaaaa..... bbbbbbbbb
ab
입력일 경우, 시간복잡도가 굉장해진다..
그러므로 시간복잡도를 줄이기 위해 stack을 이용한다.

• 문자열 S의 idx=0부터 stack에 쌓는다
• 만약, stack의 마지막 문자가 폭탄문자열의 마지막 문자와 같을경우
  - stack을 폭탄문자열 길이만큼 끝부분을 슬라이싱 한 결과가 폭탄문자열과 같을경우
  그 길이만큼 stack에서 pop!

import sys
input=sys.stdin.readline
S=list(input().rstrip())
bomb=list(input().rstrip())
len_bomb=len(bomb)
stack=[]
idx=0
while idx!=len(S):
    stack.append(S[idx])
    if stack[-1]==bomb[-1]:
        if stack[-len_bomb:]==bomb:
            for i in range(len_bomb):
                stack.pop()
    idx+=1

print(*stack if stack else "FRULA",sep="")