1. 문제 설명

문자열 폭발

2. 문제 분석

스택을 통해 현재 접근 가능한 가장 뒤의 문자에 들어오는 문자를 입력했을 때 폭발 문자가 되면 폭발 문자를 없앤다.

• 처음에는 파이썬 문자열 모듈의 find 메소드를 사용했는데 시간 초과가 나왔다. 이후 문자열을 바꾸고 인덱스를 변경하면서 시간 복잡도를 줄였는데, 워낙 문자열 자체를 변경하는 게 시간을 많이 잡아먹기 때문에 폭발 문자열 길이만큼만 문자열로 변환하고 비교하는 다음과 같은 코드가 더 효율적이었다.

• 문자열을 직접 변경하는 건 시간이 좀 걸리므로, 다른 자료구조를 활용해보자.

3. 나의 풀이

import sys
from collections import deque

s = sys.stdin.readline().rstrip()
ex_s = sys.stdin.readline().rstrip()

ex_s_len = len(ex_s)
stack = []

for letter in s:
    stack.append(letter)
    if len(stack) >= ex_s_len:
        # 스택에 폭발 문자열 길이만큼 차 있다면
        if ''.join(stack[-ex_s_len:]) == ex_s:
            # 그리고 폭발 문자열이 스택 내에 존재한다면
            for _ in range(ex_s_len):
                stack.pop(-1)
                # 스택에서 폭발 문자열을 없앤다.
                # 자동으로 스택에 들어오는 문자들은 폭발 이후 남아 있는 가장 끝부분 문자와 매칭.

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