BOJ 9935번 "문자열 폭발" 문제는 단순한 알고리즘 문제가 아니다. 이 문제를 풀다 보면 파이썬이라는 언어가 내부적으로 데이터를 어떻게 다루는지를 깊이 이해하게 된다. 알고리즘 로직이 맞아도 파이썬 특유의 메모리 복사 비용을 모르면 시간 초과를 피할 수 없기 때문이다.
이번 포스트에서는 이 문제의 최종 코드를 기준으로, 각 줄에 숨어 있는 파이썬 언어의 핵심 원리 5가지를 정리해보고자 한다.
최종 코드
먼저 완성된 코드를 보자.
import sys
input = sys.stdin.readline
st = input().strip()
bomb = input().strip()
stack = []
bomb_len = len(bomb)
for s in st:
stack.append(s)
if len(stack) >= bomb_len and "".join(stack[-bomb_len:]) == bomb:
del stack[-bomb_len:]
answer = "".join(stack)
print(answer if answer else "FRULA")
이 짧은 코드 안에 파이썬의 중요한 특성들이 고스란히 녹아 있다. 하나씩 살펴보자.
1. 가변(Mutable) vs 불변(Immutable) — 왜 문자열 대신 리스트를 쓰는가?
파이썬에서 가장 기본이 되면서 동시에 성능을 좌우하는 핵심 개념이다.
문자열(str)은 불변(Immutable) 객체다
한 번 만들어진 문자열은 내용을 수정할 수 없다. 그래서 s += "a"를 실행하면, 기존 문자열에 "a"를 붙이는 것이 아니라 아래와 같은 과정이 일어난다.
[1단계] 기존 문자열 "hello"의 전체 내용을 읽는다
[2단계] 새로운 메모리 공간을 확보한다
[3단계] "hello" + "a" = "helloa"를 새 공간에 복사한다
[4단계] 기존 "hello" 객체는 버려진다 (가비지 컬렉션 대상)
문자열이 점점 길어질수록 매번 전체를 복사하게 되므로, N번 반복하면 총 복사량이 1 + 2 + 3 + ... + N = O(N²)이 된다.
왜 이렇게 설계했을까?
불변 객체는 안전성과 최적화 측면에서 장점이 있다. 딕셔너리의 키로 사용할 수 있고, 여러 변수가 같은 문자열을 참조해도 누군가 몰래 내용을 바꿀 수 없다. 하지만 이 안전성의 대가로, 수정이 필요한 상황에서는 성능 비용을 치르게 된다.
리스트(list)는 가변(Mutable) 객체다
리스트는 메모리 주소를 유지하면서 끝에 데이터를 넣거나(append) 빼는(pop) 것이 가능하다. 기존 데이터를 복사할 필요가 없으므로, 100만 개의 데이터를 하나씩 추가해도 총 O(N) 으로 처리된다.
str += vs list.append() — 내부 동작 비교
# str += "a" (느림)
매 반복마다:
1. 새 메모리 할당 (기존 길이 + 1)
2. 기존 문자열 전체 복사
3. 새 문자 추가
4. 기존 문자열 객체 폐기
→ 총 비용: O(N²)
# list.append("a") (빠름)
매 반복마다:
1. 이미 확보된 빈 슬롯에 포인터 하나 저장
2. 끝.
→ 총 비용: O(N)
결론: 대량의 데이터를 합치거나 수정할 때는 반드시 리스트를 써야 한다.
2. 리스트의 메모리 관리 (Dynamic Array) — append()가 O(1)인 이유
"리스트에 데이터를 추가하는 게 빠르다"는 건 알겠는데, 왜 빠른 걸까? 이를 이해하려면 CPython이 리스트를 내부적으로 어떻게 구현하는지 알아야 한다.
CPython 리스트의 내부 구조
파이썬 리스트는 C 레벨에서 포인터 배열(PyObject)로 구현되어 있다. 구조를 단순화하면 다음과 같다.
PyListObject
├── ob_size : 현재 원소 개수 (예: 5)
├── allocated : 실제 확보한 슬롯 수 (예: 8)
└── ob_item : [ptr0, ptr1, ptr2, ptr3, ptr4, (빈), (빈), (빈)]
├─── 유효 데이터 ────────────┤ ├─── 여유 공간 ──┤핵심은 allocated(실제 확보한 공간)가 ob_size(실제 데이터 수)보다 항상 넉넉하게 잡혀 있다는 것이다. 이것을 Over-allocation(과할당) 이라고 한다.
Over-allocation 전략
CPython은 리스트가 꽉 찰 때마다 다음 공식으로 새 크기를 계산한다.
// CPython 소스 코드 (Objects/listobject.c)
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize;
예를 들어 현재 8개가 차 있으면, 다음 할당 크기는 약 15개 정도가 된다. 이렇게 기하급수적으로 공간을 늘리기 때문에, 재할당이 일어나는 횟수 자체가 매우 적다.
append()와 pop()이 O(1)인 이유
이 두 연산은 리스트의 맨 뒤에서만 일어난다. 앞에 있는 데이터들을 건드릴 필요가 없고, 여유 공간이 있으면 단순히 포인터 하나만 저장하면 된다.
append("x") 실행 시:
1. ob_item[ob_size] = ptr_to_x ← 포인터 하나 저장
2. ob_size += 1 ← 길이 숫자만 1 증가
→ 끝. O(1)
pop() 실행 시:
1. result = ob_item[ob_size - 1] ← 마지막 포인터 읽기
2. ob_size -= 1 ← 길이 숫자만 1 감소
→ 끝. O(1)
여유 공간이 없어서 재할당이 일어나더라도, Over-allocation 덕분에 재할당 빈도가 매우 낮아 평균적으로(Amortized) O(1)이 유지된다.
3. 슬라이싱의 함정 (Shallow Copy) — 짧은 슬라이싱 vs 긴 슬라이싱
코드에서 폭탄 문자열 일치를 확인하는 부분을 보자.
if "".join(stack[-bomb_len:]) == bomb:
stack[-bomb_len:]은 리스트의 끝부분을 복사해서 새로운 리스트를 만든다. 그런데 왜 이건 괜찮을까?
짧은 슬라이싱은 괜찮다
폭탄 문자열의 길이(bomb_len)는 최대 36이다. 따라서 stack[-36:]은 아무리 많아도 36개의 포인터만 복사한다. 스택에 100만 개의 데이터가 쌓여 있어도 이 비용은 상수에 가깝다.
긴 슬라이싱은 치명적이다
반면, 폭탄을 제거할 때 이런 코드를 쓰면 어떻게 될까?
# ❌ 절대 이렇게 하면 안 된다
stack = stack[:-bomb_len]
이 코드는 "폭탄 앞에 있는 모든 데이터"를 전부 복사해서 새 리스트를 만든다. 스택에 50만 개가 있으면 50만 개를 통째로 복사하는 것이다. 이것이 반복되면 역시 O(N²)으로 시간 초과가 발생한다.
정리
슬라이싱 복사 대상 비용
| stack[-36:] | 끝의 36개만 | O(1)에 가까움 |
| stack[:-36] | 앞의 수십만 개 전체 | O(N), 반복 시 O(N²) |
짧은 쪽을 복사하는 건 괜찮지만, 긴 쪽을 복사하는 건 치명적이다.
4. del 연산의 효율성 — 왜 슬라이싱 대입이 아니라 del을 쓰는가?
이 문제의 핵심 최적화 포인트다.
del stack[-bomb_len:]
del이 빠른 이유: CPython 내부 동작
CPython 소스 코드에서 del list[-n:]이 실행되면 내부적으로 list_ass_slice() 함수가 호출된다. 이때 일어나는 일은 매우 단순하다.
del stack[-3:] 실행 시 (스택에 10개가 있다고 가정):
Before: ob_item = [p0, p1, p2, p3, p4, p5, p6, p7, p8, p9]
↑ 여기서부터 삭제
1. p7, p8, p9의 참조 카운트(refcount)를 1 감소시킨다 → Py_DECREF()
2. ob_size = 7로 변경한다
3. 필요시 allocated를 축소한다 (list_resize)
After: ob_item = [p0, p1, p2, p3, p4, p5, p6, ?, ?, ?]
├──── 유효 데이터 ────┤ ├ 무효화 ┤
핵심: 앞에 있는 p0~p6을 건드리지 않는다. 뒤쪽 원소의 참조만 해제하고, 길이 숫자만 줄이면 끝이다. 데이터 이동(memmove)이 전혀 없기 때문에 O(n) (n은 삭제하는 개수, 즉 폭탄 길이)으로 매우 빠르다.
슬라이싱 대입이 느린 이유
# ❌ 느린 방법
stack = stack[:-bomb_len]
이 코드는 다음과 같은 과정을 거친다.
1. stack[:-3]으로 새 리스트 생성 → 7개의 포인터를 새 메모리에 복사
2. 새 리스트를 stack 변수에 바인딩
3. 기존 리스트 객체의 참조 카운트 감소 → 가비지 컬렉션 대상
7개가 아니라 50만 개라면? 매번 50만 개를 복사하게 된다. 그리고 기존 리스트를 버리고 새 리스트를 만드는 것이므로, 메모리 할당과 해제가 매번 반복된다.
for문으로 pop()을 n번 호출하면?
for _ in range(bomb_len):
stack.pop()
이 방식도 del만큼 빠르다. pop()은 앞에서 설명한 대로 ob_size를 1 줄이고 마지막 포인터를 반환하는 O(1) 연산이기 때문이다. bomb_len번 반복해도 O(bomb_len)이고, 폭탄 길이는 최대 36이므로 사실상 상수 시간이다.
del vs pop() 루프 — 미세한 차이
둘 다 충분히 빠르지만, del stack[-n:]이 약간 더 효율적이다.
del stack[-n:]
→ C 레벨에서 단 한 번의 함수 호출 (list_ass_slice)
→ 내부적으로 n개의 Py_DECREF + list_resize 한 번
for _ in range(n): stack.pop()
→ 파이썬 레벨 for 루프 오버헤드 (바이트코드 해석 비용)
→ pop() 함수를 n번 호출 (함수 호출 오버헤드 × n)
→ 각 호출마다 반환값 객체 생성 (사용하지 않더라도)
실무에서 체감할 수 있는 차이는 미미하지만, 대량 데이터를 다루는 알고리즘 문제에서는 del이 더 깔끔하고 빠른 선택이다.
세 가지 방법 비교 정리
방법 동작 비용
| del stack[-n:] | 제자리 수정, C 레벨 한 번 호출 | O(n) — 가장 빠름 |
| for _ in range(n): stack.pop() | 제자리 수정, 파이썬 루프 | O(n) — 거의 동일 |
| stack = stack[:-n] | 새 리스트 생성 + 전체 복사 | O(N) — 매우 느림 |
여기서 n은 삭제할 개수(폭탄 길이), N은 리스트 전체 길이다. 핵심 차이는 "제자리 수정이냐, 전체 복사냐"에 있다.
5. "".join(list)의 원리 — 문자열을 합치는 정석
마지막으로, 결과를 출력하는 부분이다.
answer = "".join(stack)
왜 루프 안에서 +=로 합치면 안 되는가?
1번 원리에서 설명한 것처럼, 문자열은 불변 객체다. 루프 안에서 +=를 쓰면 매번 새 문자열 객체가 생성되어 O(N²)이 된다.
join()의 내부 동작
"".join(list)이 호출되면 CPython 내부에서 다음과 같은 과정이 일어난다.
"".join(["h", "e", "l", "l", "o"]) 실행 시:
1단계: 리스트를 순회하며 각 문자열의 길이를 합산한다
→ 총 길이 = 1+1+1+1+1 = 5
2단계: 총 길이(5)에 딱 맞는 메모리를 단 한 번만 할당한다
→ [_, _, _, _, _] (5바이트 공간 확보)
3단계: 리스트의 요소를 순서대로 복사해서 채워 넣는다
→ [h, e, l, l, o]
4단계: 완성된 문자열 객체를 반환한다
→ "hello"
핵심은 메모리 할당이 딱 한 번만 일어난다는 것이다. 루프 안에서 +=를 쓰면 N번 할당이 일어나는 것과 비교하면 극적인 차이다. 이 방식이 파이썬에서 문자열을 합치는 가장 빠른 정석 방법이다.
성능 비교 예시
# ❌ 느린 방법: O(N²)
result = ""
for ch in stack:
result += ch
# ✅ 빠른 방법: O(N)
result = "".join(stack)
최종 요약 (이론 핵심)
구분 추천 방식 이유 (이론)
| 데이터 축적 | list.append() | 리스트는 가변 객체이며 O(1) 추가 가능 |
| 끝부분 삭제 | del list[-n:] 또는 pop() | 제자리 수정(In-place)으로 복사 비용 없음 |
| 일치 확인 | stack[-n:] == list(B) | 짧은 길이의 슬라이싱 복사 비용은 무시 가능 |
| 결과 출력 | "".join(stack) | 단 한 번의 메모리 할당으로 O(N)에 문자열 생성 |
이 원리들을 모르면 알고리즘 로직이 맞더라도 파이썬 특유의 메모리 복사 비용 때문에 시간 초과를 해결할 수 없다. 반대로 이 원리들을 알면, 단순히 "왜 시간 초과가 나지?"에서 벗어나 "파이썬 내부에서 무슨 일이 일어나고 있는지" 를 정확히 이해하고 코드를 설계할 수 있게 된다.
정리하면, 이 문제 하나로 파이썬의 불변/가변 객체, 동적 배열의 Over-allocation, 슬라이싱의 복사 비용, del의 제자리 수정, join의 단일 할당 전략이라는 5가지 핵심 원리를 모두 체감할 수 있다. 알고리즘 문제를 풀면서 언어 자체의 동작 원리까지 함께 공부하는 것이 실력을 키우는 가장 좋은 방법이다.
'Python study' 카테고리의 다른 글
| Python Special method (magic method) (0) | 2024.03.18 |
|---|
