백준 9935번 - 문자열 폭발

문자열 폭발 문제 바로 가기

풀이 날짜: 2026-01-29

baekjoon 알고리즘 문제 풀이

풀이 코드

word = input().strip()
find = input()
stack = []
length = len(find)

for i in word:
    stack.append(i)
    if len(stack) >= length and ''.join(stack[-length:]) == find:
        for _ in range(length):
            stack.pop()

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

문제 핵심 요약:

3190번 뱀 문제의 본질은 알고리즘 설계가 아니라 시뮬레이션이다. 매 초마다 “이동 → 충돌 검사 → 상태 갱신 → 방향 전환”이라는 규칙을 그대로 코드로 옮기는 것이 핵심이었다. BFS나 DFS처럼 모든 방향을 탐색하는 문제가 아니라, 현재 상태를 유지하면서 시간에 따라 한 방향으로만 진행하는 문제라는 점을 기억하자.

문제 핵심

이 문제의 핵심은 문자열에서 특정 폭발 문자열이 등장할 때마다 즉시 제거하고, 제거된 뒤에 새로 이어진 문자열에서도 다시 폭발이 발생할 수 있다는 점이다. 따라서 문자열을 앞에서부터 한 글자씩 처리하면서, 현재까지의 결과를 기준으로 폭발 여부를 판단해야 한다.

왜 스택(Stack)으로 접근해야 하는가

문자열 폭발은 항상 가장 최근에 추가된 문자들로 인해 발생한다. 즉, 폭발 여부는 문자열의 중간이나 앞부분이 아니라 끝부분만 검사하면 충분하다. 이 특성 때문에 자료구조 중에서도 후입선출(LIFO) 구조를 가진 스택이 가장 적합하다.

핵심 조건문이 의미하는 것

len(stack) >= flen 조건은 폭발 문자열과 비교할 수 있을 만큼 문자가 쌓였는지를 확인하는 역할을 한다. 그 다음 stack[-flen:]은 스택의 맨 뒤에서 폭발 문자열 길이만큼만 잘라낸 부분을 의미한다. 이 부분을 문자열로 변환하여 폭발 문자열과 비교함으로써, “방금 추가된 문자로 인해 폭발이 발생했는지”를 정확하게 판단할 수 있다.

폭발 문자열 제거 방식

폭발이 발생했을 때는 폭발 문자열의 길이만큼 스택에서 pop()을 반복한다. 이는 폭발 문자열이 항상 스택의 끝에 위치하기 때문이다.