[백준] 문자열 폭발 (9935번) - Python

✅ 문제 - [백준] 문자열 폭발 (9935번)

---

백준 문자열 폭발

 

✅ 처음 풀이 코드 - 시간초과

---

import sys

sentence = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()

while True:
    tmp = sentence.replace(bomb,"")

    if tmp == sentence:
        break
    sentence = tmp

if len(sentence) == 0:
    print("FRULA")
else:
    print(sentence)

bomb이 있는 경우 replace 하고

replace한 결과 tmp가 sentence랑 같은 경우 반복문을 멈춘다

 

❌ 문제점 

이런식으로 풀면 replace 메소드가 문자열의 처음부터 끝까지 순회하면 타겟을 찾으므로

문자열을 여러번 반복하게 된다.

그러므로 시간초과가 나온다

 

 

✅ 코드

---

import sys

sentence = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()


stack = []
length = len(bomb)

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

if stack:
    print(''.join(stack))
else:
    print('FRULA')

 

문자열을 처음부터 순회하며 chr를 스택에 넣어준다.

stack을 검토하며 bomb이 발견되면 stack을 pop한다.

 

문자열을 push 하고 pop 하는 게 비효율 적이어 보이지만

결국은 문자열을 처음부터 끝까지 딱 한 번만 순회하기 때문에

stack을 사용하는 것이 훨씬 효율적이다 !!!