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

문제

 

9935번: 문자열 폭발

 

 

 

 

정답 소스코드 (Python)

 

import sys
sentence=sys.stdin.readline().rstrip()
bomb=sys.stdin.readline().rstrip()
bomb_len=len(bomb)
stack=[]
for i in range(len(sentence)):
    stack.append(sentence[i])
    if ''.join(stack[-bomb_len:])==bomb:
        for j in range(bomb_len):stack.pop()


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

 

 

풀이  (Python)

 

 

첫 풀이에서는 문자열 관련 문제로 파악하여 간단히 문자열 슬라이싱 또는 문자열 raplace함수를 사용하여 풀이하였다.

sentence=input()
bomb=input()
while bomb in sentence:sentence=sentence.replace(bomb,"")
if sentence:print(sentence)
else:print("FRULA")

하지만 이와 같이 풀이 시에 시간초과의 문제가 발생한다. replace시에 해당 문자열 길이의 시간복잡도가 발생하는 것 같다.

이를 어떻게 해결해야할까?

 

 

Point 1)  폭발 문자열은 한 번에 폭발한다.

첫 풀이에서 한번에 폭발하는 것과 한 개씩 replace 하는 것이 차이가 없다고 생각했었는데, 모든 폭발 문자열이 폭발하는 것은 시간초과의 문제가 발생하는 것을 해결하는 힌트였다.

 

이를 바탕으로 stack을 사용하여 아래와 같이 코드를 구성하였다.

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

 

가능한 폭발 문자열의 개수를 K라고 임의로 할 때, 밖의 for문의 전체 시간복잡도는 문자열 길이인 S이다.

첫 풀이의 경우 폭발 문자열의 개수 만큼 while문을 반복기 때문에 해당 로직의 시간복잡도는 O(|S|*K)이다.

stack을 이용하는 경우에는 폭발 문자열을 제거하는 것이 상수 시간이기에 시간복잡도가 O(|S|)에 가능한 것이다.