🟩 [백준] [Python] [Gold4] 9935번_문자열 폭발

문제

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

9935번: 문자열 폭발

풀이

# 백준 9935번 문제 - 문자열 폭발
import sys
input = sys.stdin.readline
# 입력값 처리
s = input().rstrip()
bomb = input().rstrip()

# stack으로 문자열 폭발 구현
stack = []
bomb_length = len(bomb)

for char in s:
    stack.append(char)
    if ''.join(stack[-bomb_length:]) == bomb:
        for _ in range(bomb_length):
            stack.pop()

# 결과 출력
if stack:
    print(''.join(stack))
else:
    print('FRULA')

문자열 함수를 사용하면 O(n^2) 이기 때문에 시간초과가 발생한다. 

스택 자료구조를 사용해서 해결을 하였다.