문제 보기 · Level 3 · 2023 KAKAO BLIND RECRUITMENT · 정답률 35% · 푼 사람 5,215명 (2026-09-30 기준)1
문제
이진트리를 수로 바꾸는 방법이 있다. 트리에 더미 노드를 더해 포화 이진 트리로 만들고(루트는 그대로), 노드를 가장 왼쪽부터 오른쪽으로 보며 더미면 0, 진짜 노드면 1을 이어 적는다. 이 이진수를 십진수로 바꾼다. 노드의 왼쪽·오른쪽은 “왼쪽 아래 나무 < 노드 < 오른쪽 아래 나무” 순서다. 수들이 주어질 때, 각 수를 어떤 이진트리로 만들 수 있으면 1, 없으면 0을 담아 돌려준다.
- 수 1 ~ 10,000개, 각 수는 1 이상 10¹⁵ 이하
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 트리 순회와 이진 탐색 트리: “가장 왼쪽부터 오른쪽으로” 보는 순서는 중위 순회다. 포화 이진 트리를 중위 순서로 늘어놓으면 뿌리가 한가운데다.
- 비트 연산과 비트마스크:
bin(x)로 이진수 문자열을 얻는다. - 진법과 자릿수:
bin(x)[2:]의 길이는 x의 2진 자릿수 ⌊lg x⌋ + 1이라, 10¹⁵ 이하의 수는 50자리 이하다. 앞에 0을 붙여도 수는 그대로라zfill로 칸 수를 맞춰도 된다.
1단계 · 작은 예로 손으로 풀기
문제의 예에서 트리를 포화 이진 트리(칸 7개)로 채운 뒤 왼쪽부터 읽으면 0111010, 곧 58이다. 거꾸로 58이 주어지면:
- 이진수
111010(6자리)을 칸 7개에 맞게 앞에 0을 붙여0111010으로 만든다. - 한가운데(4번째)
1이 뿌리다. 왼쪽011, 오른쪽010이 두 자식 나무다. 011의 가운데1이 왼쪽 자식이고, 그 왼쪽0(더미), 오른쪽1(진짜)이다.
이렇게 모두 진짜 노드 아래에만 진짜 노드가 있으면 트리가 된다. 5 = 101은 가운데(뿌리)가 0, 곧 더미인데 그 아래에 진짜 노드 1이 있어 트리가 될 수 없다.
2단계 · 가장 단순한 방법과 그 속도
가능한 트리를 모두 만들어 수를 모아 두는 방법은, 10¹⁵까지면 칸이 63개라 트리 수가 폭발한다. 반대로 수 하나를 받아 거꾸로 트리를 읽으면, 칸 63개를 한 번씩 보면 된다.
3단계 · 핵심 아이디어
- 칸 수 맞추기: 포화 이진 트리의 칸 수는 1, 3, 7, 15, 31, 63, …(2ᵏ − 1)이다. 이진수 길이 이상인 가장 작은 칸 수로 앞에 0을 채운다. 2ᵏ − 1이 나오는 까닭은 k층 트리의 칸이 층마다 1, 2, 4, …로 두 배씩 늘어 등비급수 1 + 2 + ⋯ + 2ᵏ⁻¹을 이루기 때문이다.
- 더 큰 틀은 안 된다: 한 단계 더 큰 틀에 넣으면 앞에 붙는 0이 틀의 절반을 넘어, 한가운데(뿌리)가 0이 된다. 뿌리가 더미인데 아래에 1이 있으니 늘 안 된다. 그래서 가장 작은 틀 하나만 보면 된다.
- 규칙: 더미 노드는 빈자리를 채우려고 넣은 것이라, 더미 아래에 진짜 노드가 있을 수 없다. 그래서 어떤 나무의 뿌리(가운데)가 0이면 그 나무 전체가 0이어야 한다. 뿌리가 1이면 왼쪽 절반과 오른쪽 절반을 같은 규칙으로 확인한다.
4단계 · 코드 흐름
- 수마다
bin(x)[2:]로 이진수 문자열을 만든다. - 길이 이상인 가장 작은 2ᵏ − 1을 구하고,
zfill로 앞에 0을 채운다. - ok(s): 길이 1이면 참. 가운데가 0이면 “s에 1이 없나”를 돌려준다. 가운데가 1이면 왼쪽 절반과 오른쪽 절반이 모두 ok인지 돌려준다.
- 결과를 1 또는 0으로 모은다.
5단계 · 파이썬 코드
def solution(numbers):
def ok(s):
if len(s) == 1:
return True
mid = len(s) // 2
if s[mid] == "0": # 뿌리가 더미면
return "1" not in s # 아래도 모두 더미여야 한다
return ok(s[:mid]) and ok(s[mid + 1:])
answer = []
for x in numbers:
b = bin(x)[2:]
size = 1
while size < len(b): # 1, 3, 7, 15, …
size = size * 2 + 1
answer.append(1 if ok(b.zfill(size)) else 0)
return answer
bin(58)은'0b111010'이다.[2:]로 앞의0b를 뗀다.b.zfill(7): 길이가 7이 되도록 앞에 0을 채운다.size * 2 + 1: 포화 이진 트리에 층을 하나 더하면 칸 수가 2배 + 1이 된다. k층의 칸 수 sₖ는 s₁ = 1, sₖ = 2sₖ₋₁ + 1인 선형 점화식이고, 하노이의 탑과 같은 꼴이다.
6단계 · 실행 추적
| 수 | 이진수 | 채운 문자열 | 확인 과정 | 결과 |
|---|---|---|---|---|
| 7 | 111 | 111 | 가운데 1 → 양쪽 1, 1 |
1 |
| 42 | 101010 | 0101010 | 가운데 1 → 왼쪽 010(가운데 1, 양쪽 한 칸), 오른쪽 010도 같음 |
1 |
| 5 | 101 | 101 | 가운데 0인데 1이 있음 | 0 |
| 95 | 1011111 | 1011111 | 가운데 1 → 왼쪽 101의 가운데가 0인데 1이 있음 |
0 |
답은 [1, 1, 0]과 [1, 1, 0](63, 111, 95)이다.
7단계 · 복잡도와 흔한 실수
수 하나에 칸이 많아야 63개이고, 확인은 칸 수 × 층 수(약 6) 정도다. 수 1만 개도 금방 끝난다.
- 앞에 0을 채우지 않고 원래 길이로 가운데를 잡는다.
- “뿌리가 0이면 바로 불가능”으로 판단한다. 뿌리가 0이어도 그 나무 전체가 0이면 된다(더미로만 된 나무).
- 칸 수를 2의 거듭제곱(2, 4, 8, …)으로 맞춘다. 포화 이진 트리는 2ᵏ − 1칸이다.
검증: 문제의 예시 2개와 58의 문자열을 확인했다. 칸 1, 3, 7, 15개 틀에서 “뿌리를 포함하고 부모가 있어야 자식이 있는” 모든 나무(706개)를 만들어, 1부터 2¹⁵ − 1까지 모든 수에서 풀이의 답과 비교해 같았다. 10¹⁵이 50비트라 63칸 틀에 들어가는 것과 1만 개의 시간도 확인했다 — 29_pg150367_p1.py