💻 백준 9935번: 문자열 폭발

문제 소개 🧐

문자열 안에 포함된 특정 ‘폭발 문자열’을 제거하는 문제입니다. 폭발 문자열이 터지면 해당 부분은 사라지고, 남은 문자열들이 합쳐집니다. 이 과정은 더 이상 폭발할 문자열이 없을 때까지 반복됩니다. 모든 폭발이 끝난 후 남은 문자열을 출력해야 합니다.

입력 📝

  • 첫째 줄에 원본 문자열 (길이 1 ~ 1,000,000)
  • 둘째 줄에 폭발 문자열 (길이 1 ~ 36)

출력 📤

  • 최종적으로 남은 문자열을 출력합니다. 남은 문자열이 없으면 “FRULA”를 출력합니다.

제한 ❌

  • 시간 제한: 2초
  • 메모리 제한: 128MB

첫 번째 시도: replace 반복 😭

Idea

그냥 bomb이 없을때까지 replace 해보자 (시간 복잡도가 초과할거 같긴하다…)

Code

import sys

org_string = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()
LEN = len(bomb)

while True:
    prev_org = org_string
    org_string = org_string.replace(bomb, '')

    if prev_org == org_string:
        break

org_string = 'FRULA' if org_string == '' else org_string

print(org_string)

Result

  • 결과: 시간초과 (46%) 😭
  • 예상대로였다. replace() 함수는 매번 문자열 전체를 탐색하고 새로운 문자열을 생성하므로, 문자열의 길이가 길고 폭발이 여러 번 일어나야 하는 경우 매우 비효율적이다.

두 번째 시도: deque와 stack 조합 😭

Idea

stack과 deque으로 한번의 순회에 끝낼 수 있도록 해보자

Code

import sys
from collections import deque

org_string_q = deque(sys.stdin.readline().rstrip())
bomb = list(sys.stdin.readline().rstrip())
LEN_ORG, LEN_BOMB = len(org_string_q), len(bomb)
stack = []

b_idx = 0
bomb_processing = False
while org_string_q:
    let = org_string_q.popleft()
    stack.append(let)

    if let == bomb[b_idx]:
        b_idx += 1
        bomb_processing = True
    
    if bomb_processing and b_idx == LEN_BOMB:
        for i in range(b_idx):  # 폭탄 만큼 빼기
            stack.pop()
        idx = 0
        while stack and idx < LEN_BOMB:
            next_start_let = stack.pop()
            org_string_q.appendleft(next_start_let)
            idx += 1
        b_idx = 0

if stack:
    print(*stack, sep='')
else:
    print('FRULA')

Result

  • 결과: 실패 😭
  • 어림 없었다. 로직이 너무 복잡해졌고, 폭발 후 stack의 문자를 다시 deque로 옮기는 과정에서 처리해야 할 엣지 케이스가 많아 올바르게 동작하지 않았다.

세 번째 시도: 스택을 이용한 단순화 ✨

Idea

그냥 스택에 계속 append 하고, 매 회 스택의 윗부분부터 비교하면 어떨까?

Code

import sys

org_string = list(sys.stdin.readline().rstrip())
bomb = list(sys.stdin.readline().rstrip())
LEN_BOMB = len(bomb)
stack = []

for let in org_string:
    stack.append(let)
    if stack[-1*LEN_BOMB:] == bomb:
        for _ in range(LEN_BOMB):
            stack.pop()

if stack:
    print(*stack, sep='')
else:
    print("FRULA")

Result

  • 결과: 성공! 🎉
  • 이 방법은 문자열을 단 한 번만 순회하며, 각 문자마다 스택의 마지막 부분만 확인하면 되므로 매우 효율적이고 간단한 해결책이었다.

마무리 🤔

  • 자료구조의 중요성: 문제의 요구사항을 분석하고 그에 맞는 적절한 자료구조(이 경우 스택)를 선택하는 것이 얼마나 중요한지 다시 한번 깨달았다.
  • 시간 복잡도: replace()와 같은 편리한 함수가 내부적으로 어떻게 동작하는지, 그리고 그것이 전체 알고리즘의 시간 복잡도에 어떤 영향을 미치는지 항상 고려해야 한다.

복잡하게 생각했던 문제를 스택 하나로 간단하게 풀 수 있었다. 마지막에 추가된 문자들을 다루는 문제에서는 스택을 우선적으로 떠올려봐야겠다.

⁂