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

문제

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

💻 초기 풀이 과정

1. 초기에는 stack의 자료구조를 활용하지않고, 파이썬 문자열 내장함수인 replace를 활용했다
   2 . replace를 활용할때, 최악의 경우 O($N^2$)가 되어 시간 초과가 발생했다.
2. 따라서 stack 구조를 이용해 폭발 문자열을 발견했을 때, 폭발 문자열의 길이만큼 pop() 하도록 다시 구현했다.
3. 이때 제일 안쪽에 있는 for 문의 경우 폭발 문자열의 길이가 1~36으로 작아서 상수 시간 안에 처리될 수 있다.

틀린 코드

import sys
input=sys.stdin.readline

a=input().rstrip()
bomb=input().rstrip()
i=0
count=len(a)//len(bomb)
while i<count:
    i+=1
    if len(a)==0:
        break
    else:
        a=a.replace(bomb,'')
    

if len(a)==0:
    print("FRULA")
else:
    print(''.join(a))

정답 코드

import sys
input=sys.stdin.readline

a=input().rstrip()

bomb=input().rstrip()
stack=[]

count=len(bomb)
for i in range(len(a)):
    stack.append(a[i])
    if ''.join(stack[-count:]) == bomb:
        for _ in range(count):
            stack.pop()
    
if stack:
    print(''.join(stack))
    
else:
    print("FRULA")
    

정리

문자열 관련 문제에서 내장 함수를 활용하는 건 항상 최적의 선택이 될 수 없다. 오히려 내장함수를 사용하는 것이 최악이 될 수 있다.
따라서 해당 문제의 시간 복잡도를 잘 고려해서, 내장 함수를 사용하자