[백준] 문자열 폭발

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

9935번: 문자열 폭발

 

문자열을 뿌요뿌요처럼 문자열안에 특정 문자열이 나올 경우에 폭발 시키는 문제입니다.

처음에는 반복문으로 문자열.find(찾을문자열)로 문자열을 지워주는 방법으로 했는데 이 방법은 시간초과가 걸린다.

find의 시간복잡도는 O(n)이기 때문에 반복적으로 find를 돌리면 시간이 오래 걸린다.

stack을 이용하면 문자열을 한번만 돌며 해결을 할 수 있다.

 

def boom(s, bomb):
    stack = []
    for i in s:
        stack.append(i)
        if "".join(stack[-len(bomb):]) == bomb:
            del stack[-len(bomb):]
    return "".join(stack) if len(stack) != 0 else "FRULA"

s = input()
bomb = input()
print(boom(s,bomb))