[백준] 9935번 문자열 폭발 -python 파이썬 (시간초과 해결)

문제

 

 

 

이 문제에서 가장 유의해야할 점은 시간복잡도이다 왜냐하면 첫째줄에 주어지는 문자열의 길이의 범위가 굉장히 크기때문이다. (그래서 초반엔 시간복잡도 오류가 많이 발생함;;)


먼저 이 문제를 어떤 알고리즘으로 풀어야할지 생각을 해본다면 단순히 폭발문자열이 들어가있는 때는 간단하지만 "CC44"처럼 연속해서 오는경우가 까다로워 진다. (while문으로 없을 때까지 확인하면 시간초과가 발생)


그런데 이 문제 잘 생각해보면 괄호여닫기와 굉장히 유사하다는 것을 알 수 있다. 그래서 stack 을 사용하면 이 문제를 풀 수 있다.

 

 

for 문으로 첫번째 문자열을 돌면서 폭발문자열이 들어가면 pop해주는 형식으로 구현해주면 된다.

 

이때 구현하면서 한가지 실수를 했는데

 

 

 

오답코드

 

string  = input()
bomb = input()
ls = len(string)
lb = len(bomb)
arr = list(string)
stack = []

for i in range(ls):
    stack.append(arr[i])
    if bomb in ''.join(stack):
        for _ in range(lb):
            stack.pop()

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

 

 

이때 

 

if bomb in ''.join(stack)

 

 

이 부분이 문제가 됐다. 이렇게 구현하게 되면 join을 할 때마다 stack 전부 돌면서 찾아줘야하기때문에 시간복잡도가 높아지게 된것

 

 

 

정답코드

 

S  = input()
bomb = input()
ls = len(S)
lb = len(bomb)

stack = []

for i in range(ls):
    stack.append(S[i])
    #stack의 마지막인덱스부터 폭탄문자열의 길이만큼 확인
    if bomb == ''.join(stack[-lb:]):
        for _ in range(lb):
            stack.pop()

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

 

 

 

이렇게 stack 마지막 문자열부터 폭탄문자열길이만큼만 가져오도록 수정해주었다.

 

내장함수를 사용할 때의 시간복잡도를 생각하지 못해서 발생한 실수였다....