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

문제

 

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

9935번: 문자열 폭발

 

 

 

문제 풀이

 

폭탄 문자열이 입력 문자열에 없을 때까지 replace함수를 이용해 폭탄문자열을 ''로 대체했다.

 

하지만 시간초과가 났다... 아무래도 내장함수를 사용하는 것이 시간이 오래 소요되는 것 같다.

 

import sys

s=input()
bomb=input()

while bomb in s:
    s=s.replace(bomb,'')

if s=='':
    print('FRULA')
else:
    print(s)

 

 

 

그래서 replace 함수를 사용하지 않고, 스택을 사용해 폭탄 문자열을 찾아서 없애주었다.

 

1. 입력받은 문자열을 스택에 하나씩 저장한다.

 

2. 이 때, 시간복잡도를 줄이기 위해서 폭탄문자열의 첫번째부터 일치하는 지 따지는 것이 아니라 마지막번째와 일치하는 지 체크한다. 

 

3. 마지막번째 문자와 일치하는 경우에만, 폭탄문자열 전체와 일치하는 지 비교해주면 되기 때문에 시간복잡도를 줄일 수 있다.

 

4. 폭탄문자열과 일치한다면, 스택에서 폭탄문자열의 길이만큼 pop을 해준다.

 

import sys
s=input()
bomb=list(input())
l=len(bomb)
stack=[]
for x in s:
    stack.append(x)
    if x==bomb[-1]:
        if bomb==stack[-l:]:
            for _ in range(l):
                stack.pop()
if stack==[]:
    print('FRULA')
else:
    print(''.join(stack))