[백준] 9935. 문자열 폭발

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

9935번: 문자열 폭발

그냥 완전 탐색으로 풀었더니 당연히 시간초과가 났다. 스택을 생각했다가 어떻게 활용해야 될지 모르겠어서 패스 했는데 알고리즘 분류에도 스택이 있길래 다시 도전했다. 스택으로 한참 생각해보니까... 의외로 쉬워서 당황 ㅋㅋ 스택 수열 풀때랑 비슷..? 하게 일단 스택에 넣고 확인하는 게 답이었다.

 

일단 스택에 집어 넣은 뒤, 스택의 top과 bomb의 마지막 글자가 같고 스택의 길이가 bomb의 길이보다 크거나 같고 bomb와 stack안에 든 글자가 같으면! while문으로 stack.pop()을 해준다. pop 해줄 때 좀 더 효율적인 방법이 있을 것 같은데 거기까지 생각이 잘 안 난다. 진짜 알고리즘은 자료구조를 얼마나 자유자재로 잘 활용하는가에 따라서 효율이 확 달라지는 것 같다.

import sys
input = sys.stdin.readline
sentence = input().rstrip()
bomb_sen = input().rstrip()

stack = []

for char in sentence:
    stack.append(char)
    if char == bomb_sen[-1] and len(stack) >= len(bomb_sen) and ''.join(stack[-len(bomb_sen):]) == bomb_sen :
        cnt = 0
        while cnt < len(bomb_sen):
            stack.pop()
            cnt += 1

if stack:
    print(''.join(stack))

else:
    print('FRULA')