[백준/Python] 9935 문자열 폭발

문제는 여기

코드

1차 코드

import sys
input = sys.stdin.readline

word = input().strip()
bomb = input().strip()

while word.find(bomb) > -1:
    word = word.replace(bomb,'')

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

파이썬이 주언어라면 떠올릴 find와 replace를 통한 접근 ...
47%에서 시간초과가 났다

2차 코드

import sys
input = sys.stdin.readline
compare = []

stack = input().strip()
bomb = input().strip()

for i in range(len(stack)):
    compare.append(stack[i])
    temp = ''.join(map(str,compare))
    if bomb in temp:
        for _ in range(len(bomb)):
            compare.pop()

if compare:
    print(''.join(compare))
else:
    print("FRULA")

정답에 근접했다고 생각한다
in 연산자의 평균 시간 복잡도는 O(n)이다.
근데 나는 for문 -> in연산자 -> for문 (..)으로 코드를 작성했다
결론 : 시간 초과

정답 코드

for i in range(len(stack)):
    compare.append(stack[i])
    if ''.join(compare[-len(bomb):]) == bomb:
        for _ in range(len(bomb)):
            compare.pop()

for문 부분만 변경했다
문자열을 담았던 배열(compare)을 끝에서부터 폭발될 문자열의 크기만큼 자르고,
그게 폭발 문자열과 같은 경우 pop해주었다.

아오 😇
끝