[백준] 9935번 - 문자열 폭발 (파이썬)

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

# 문자열 폭발
str = input().strip()
bomb = list(input().strip())

result = []
for i in range(len(str)):
    result.append(str[i])
    if result[-len(bomb):] == bomb:
        for _ in range(len(bomb)):
            result.pop()
if result:
    print(*result, sep='')
else:
    print('FRULA')

 

자료구조 (스택)

1. result에 문자열을 하나씩 넣는다

2. 만약 result의 뒤에서 bomb길이 만큼의 문자열이 bomb와 같으면 bomb의 길이만큼 pop을 해준다.

3. result가 빈 문자열이면 'FRULA'를 아니면 result를 출력

 

기존의 파이썬 문자열의 replace를 이용하면 최악의 경우 O(N^2)으로 시간초과가 나온다

큐를 이용해서 O(N)으로 해결할 수 있다.