폭탄 문자열 제거란?
문자열에서 정해진 '폭발 패턴' 이 연속으로 나타날 때마다 그 부분을 제거하고, 양옆이 붙으면서 또 생기는 패턴까지 모두 사라질 때까지 반복하는 문제입니다.
예를 들어 젤리 줄 "mirkAAkkx"에서 폭발 패턴이 "kk"라면, 가운데 kk가 펑 하고 터지면서 "mirkAAx"가 남습니다.
왜 스택일까?
가장 단순한 방법은 "패턴을 찾아 지우고, 처음부터 다시 검사"를 반복하는 것입니다. 하지만 이렇게 하면 제거할 때마다 문자열 전체를 다시 훑어야 해서, 최악의 경우 O(n²) 이상으로 매우 느려집니다.
핵심 통찰: 폭발은 항상 방금 쌓은 글자들의 끝부분에서 일어납니다. 앞쪽은 이미 검사가 끝났고, 새 글자가 들어오면서 새로운 패턴이 생긴다면 그건 반드시 맨 끝에서 생깁니다.
그래서 스택을 씁니다. 글자를 하나씩 스택에 쌓다가, 스택의 맨 위 K개가 폭발 패턴과 같아지는 순간 그 K개를 한 번에 pop하면 됩니다. 양옆이 붙으면서 생기는 연쇄 폭발도 자동으로 처리됩니다 — pop하고 나면 그 아래에 있던 글자들이 자연스럽게 새로운 끝부분이 되니까요.
동작 원리
1단계. 문자를 왼쪽부터 하나씩 스택에 push합니다.
2단계. push한 직후, 방금 넣은 글자가 폭발 패턴의 마지막 글자와 같은지 확인합니다. (다르면 절대 패턴을 완성할 수 없으니 비교 자체를 건너뜁니다 — 작은 최적화)
3단계. 같다면 스택 끝 K개를 폭발 패턴과 비교합니다.
- •일치하면 끝 K개를 pop (펑!)
- •다르면 그대로 둡니다.
4단계. 끝까지 진행한 뒤 스택에 남은 글자가 정답입니다. 비어 있으면 "EMPTY".
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n) |
| 공간 | O(n) |
각 글자는 최대 한 번 push되고 최대 한 번 pop됩니다. 문자열을 단 한 번만 훑으므로 전체 O(n)입니다.
자주 하는 실수
- •매번 처음부터 다시 검사: 패턴을 지운 뒤 0번 인덱스부터 다시 스캔하면 O(n²). 스택으로 끝부분만 보세요.
- •문자열 + replace 반복:
while (s.contains(bomb)) s = s.replace(...)는 직관적이지만 매우 느립니다. - •K개 비교를 매 글자마다: 방금 넣은 글자가 패턴 마지막 글자와 다르면 비교를 건너뛰어 상수를 줄일 수 있습니다.
알고노트에서 직접 확인하세요
글자가 스택에 하나씩 쌓이고, 끝부분이 폭발 패턴과 일치하는 순간 펑 하고 터지는 과정을 알고노트에서 단계별로 볼 수 있습니다.