[PS] BOJ 9935 / 문자열 폭발

Minjun Kim

17 Jul 2025 • 1 min read

문제 링크: https://www.acmicpc.net/problem/9935

Thumbnail: Photo by Katelyn G (Unsplash)

스택을 활용하는 간단한 문제입니다.

풀이

문자열이 폭발한다! 💥

전체 문자열에서 "폭발 문자열"이 존재한다면, 그 부분만 폭발하고 사라집니다. 모든 폭발 문자열이 사라지고 난 뒤의 문자열을 찾는 문제입니다.

전체 문자열에서 한 문자 씩 스택에 쌓고, 현재 스택에 쌓인 문자들을 끝에서부터 폭발 문자열의 길이만큼 비교해 봅니다. 이때, 비교한 내용이 폭발 문자열과 일치한다면, 해당 내용을 스택에서 제거합니다.

이 과정을 전체 문자열의 끝까지 반복한 뒤, 스택에 남은 문자열을 출력하면 됩니다.
만약, 모든 폭발 문자열을 지운 결과 스택이 비어있다면 "FRULA"를 출력합니다.

전체 코드

from collections import deque
input = open(0).readline
text = input().strip()
bomb = input().strip()
text_len = len(text)
bomb_len = len(bomb)

stack = deque()
i = 0
s = 0
while i < text_len:
    stack.append(text[i])

    # 현재 스택의 맨 끝에 폭발 문자열이 있는지 검사
    b_i = bomb_len - 1
    s_i = s
    while s >= bomb_len - 1 and  b_i >= 0:
        if stack[s_i] != bomb[b_i]:
            break
        s_i -= 1
        b_i -= 1
    if b_i < 0:
        # 문자열 폭발!
        for _ in range(bomb_len):
            stack.pop()
            s -= 1
    i += 1
    s += 1

print("".join(stack) if stack else "FRULA")

solution.py