★Stack & Queue & Deque Advanced I - 1 Solved★

★ 9935 문자열 폭발 ★

 

import sys
input=sys.stdin.readline
s=list(input().rstrip())
explode=list(input().rstrip())
explode_length=len(explode)
ans=[]

for x in range(len(s)):
    ans.append(s[x])
    if s[x] == explode[-1]:
        if explode_length<=len(ans) and ans[-explode_length:] == explode:
            for _ in range(explode_length):
                ans.pop()
if not ans:
    print('FRULA')
else:
    print(*ans,sep='')

 

😮 폭발 문자열의 길이가 최대 36이므로, 문자열을 계속 ans에 넣다가 맨 마지막 폭발 문자열이 들어갈 경우, 앞선 들어간 문자열이 폭발 문자열이 맞다면 pop() 연산으로 빠르게 삭제. 그리고 계속 update. stack에 넣고 빼는 연산 O(1)을 활용해 시간 복잡도 최대 O(N)

---