[백준/Python] 9935번. 문자열 폭발

문제

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

 

 

풀이

문자열에서 폭발 문자열이 없어질때까지 반복해서 찾아 지워나간다면 이론적으로 풀리기야 하겠지만 시간이 초과된다.

 

스택을 이용하면 전체 문자열에서 폭발 문자열을 찾는데 소요되는 시간, 문자열에서 폭발문자열을 반복하며 도려내어 새로운 문자열을 만드는 시간을 단축하여 빠르게 해결이 가능하다.

 

문자열을 앞에서부터 한글자씩 끝까지 순회하며 스택에 push하면서 스택의 윗부분과 폭발 문자열이 일치한다면 폭발 문자열의 길이만큼 pop해주기만 하면 한번의 순회로 쉽게 해결이 가능하다.

 

 

 

 

정답 코드

msg = input()
bomb = list(input())

answerStack = []
for letter in msg:
    answerStack.append(letter)
    if len(answerStack) >= len(bomb):
        if answerStack[-len(bomb):] == bomb:
            for _ in range(len(bomb)):
                answerStack.pop()

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

 

시간초과 코드

msg = input()
bomb = input()

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

if msg != '':
    print(msg)
else:
    print("FRULA")