[백준] 9935 문자열 폭발 / 구현 / Python 골4

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

 

처음에 파이썬 replace로 비벼보려고 했는데, 칼같이 시간초과 나온대서 포기;;

 

다른 블로그 아이디어를 참고했다

 

stack에 문자열 요소를 하나씩 집어넣으면서

그때마다 stack의 가장 최근에 집어넣어진 요소를 기준으로 폭발문자열 길이만큼 탐색했을 때

그 문자열이 폭발문자열과 일치하면 stack에서 폭발문자열 길이만큼 pop하며 지워준다

 

stack이 비어있으면 FRULA를 출력하고

그렇지 않으면 stack을 join을 써서 문자열로 만들어 출력한다

 

s = input()
bomb = input()
b = len(bomb)
stack=[]
for el in s:
    stack.append(el)
    if ''.join(stack[-b:])==bomb:
        for _ in range(b):
            stack.pop()

result = ''.join(stack)

if result:
    print(result)
else:
    print("FRULA")