문제 보기 · Level 3 · 2019 KAKAO BLIND RECRUITMENT · 정답률 40% · 푼 사람 9,734명 (2026-09-30 기준)1
문제
이진 트리의 노드 좌표 [x, y]가 1번 노드부터 주어진다. 규칙은 이렇다.
- 모든 노드의 x는 서로 다르다. 같은 층의 노드는 y가 같고, 자식의 y는 부모보다 작다.
- 어떤 노드 V의 왼쪽 아래 나무의 x는 모두 V의 x보다 작고, 오른쪽 아래 나무의 x는 모두 V의 x보다 크다.
이 트리를 전위 순회, 후위 순회한 노드 번호 목록을 [전위, 후위]로 돌려준다.
- 노드 1 ~ 10,000개, 좌표 0 ~ 100,000
- 트리의 깊이는 1,000 이하
풀이
막히면 한 단계씩 펼친다.
필요한 개념
- 트리 순회와 이진 탐색 트리: 두 번째 규칙은 x를 열쇠로 한 이진 탐색 트리의 규칙과 같다. 위층부터 차례로 넣으면 트리가 그대로 만들어진다.
- 부분순서와 위상 정렬: “위층부터”는 “조상이 자손보다 먼저”를 지키는 순서(위상 정렬) 가운데 하나다. 이 조건만 지키면 어느 순서로 넣어도 같은 트리가 나온다2.
1단계 · 작은 예로 손으로 풀기
노드 A(5, 3), B(3, 1), C(8, 1)이 있다고 하자.
- y가 가장 큰 A가 뿌리다(자식은 부모보다 아래).
- B는 x가 3 < 5라 A의 왼쪽, C는 8 > 5라 A의 오른쪽이다.
전위는 A, B, C, 후위는 B, C, A다. “위층부터 하나씩, x를 비교해 왼쪽·오른쪽으로 내려가 빈자리에 넣기”가 곧 이진 탐색 트리에 넣기다.
2단계 · 가장 단순한 방법과 그 속도
뿌리를 찾고(y가 가장 큰 노드), 나머지를 x로 왼쪽·오른쪽 무리로 나눠 같은 일을 되풀이할 수 있다. 무리를 나눌 때마다 전부 훑으니, 한 층에 \(O(n)\)씩 깊이 1,000층이면 최악 약 1,000만 번이다. 재귀가 깊이 1,000까지 내려가 파이썬 기본 재귀 한도(1,000)에도 걸린다.
3단계 · 핵심 아이디어
- 위층부터 넣기: 노드를 y가 큰 순서로 정렬해 이진 탐색 트리에 차례로 넣는다. 부모는 늘 자식보다 위층이라 먼저 들어가 있다. 그래서 넣을 때 내려가다 만나는 빈자리가 곧 문제의 트리에서의 자리다.
- 자식은 딕셔너리로: left[v], right[v]에 왼쪽·오른쪽 자식 번호를 적는다.
- 순회는 스택으로: 깊이가 1,000이라 재귀 대신 스택을 쓴다.
- 전위(뿌리 → 왼쪽 → 오른쪽): 꺼낸 노드를 적고, 오른쪽 자식을 먼저 넣고 왼쪽 자식을 나중에 넣는다. 스택은 나중에 넣은 것을 먼저 꺼내니 왼쪽이 먼저 나온다.
- 후위(왼쪽 → 오른쪽 → 뿌리): “뿌리 → 오른쪽 → 왼쪽” 순서로 적은 뒤 뒤집으면 된다. 전위와 같은 방식에서 넣는 순서만 바꾼다. 이것이 늘 맞는다는 것은 구조적 귀납법으로 보인다. 빈 나무는 두 목록이 모두 비어 있다. 큰 나무의 “뿌리 → 오른쪽 → 왼쪽” 목록은 (뿌리, 오른쪽 나무의 목록, 왼쪽 나무의 목록)이고, 이를 뒤집으면 (뒤집은 왼쪽 목록, 뒤집은 오른쪽 목록, 뿌리)다. 두 작은 나무에서 뒤집은 목록이 후위라고 두면, 이것은 (왼쪽 후위, 오른쪽 후위, 뿌리), 곧 큰 나무의 후위다.
4단계 · 코드 흐름
- 노드 번호를 (y 큰 순, 같으면 x 작은 순)으로 정렬한다. 첫 노드가 뿌리다.
- 나머지 노드를 차례로 뿌리부터 x를 비교하며 내려가, 비어 있는 left 또는 right에 넣는다.
- 스택으로 전위 순회를 한다.
- 스택으로 “뿌리 → 오른쪽 → 왼쪽”을 적은 뒤 뒤집어 후위를 만든다.
- 번호를 1부터로 바꿔 [전위, 후위]를 돌려준다.
5단계 · 파이썬 코드
def solution(nodeinfo):
nodes = sorted(range(len(nodeinfo)), key=lambda i: (-nodeinfo[i][1], nodeinfo[i][0]))
left, right = {}, {}
root = nodes[0]
for i in nodes[1:]: # x를 열쇠로 넣는다
cur = root
while True:
if nodeinfo[i][0] < nodeinfo[cur][0]:
if cur not in left:
left[cur] = i
break
cur = left[cur]
else:
if cur not in right:
right[cur] = i
break
cur = right[cur]
pre, post = [], []
stack = [root] # 전위
while stack:
v = stack.pop()
pre.append(v + 1)
if v in right: stack.append(right[v])
if v in left: stack.append(left[v]) # 왼쪽을 나중에 넣어 먼저 꺼낸다
stack = [root] # 뿌리 → 오른쪽 → 왼쪽
while stack:
v = stack.pop()
post.append(v + 1)
if v in left: stack.append(left[v])
if v in right: stack.append(right[v])
post.reverse() # 뒤집으면 후위
return [pre, post]
key=lambda i: (-nodeinfo[i][1], nodeinfo[i][0]): y에 −를 붙여 큰 y가 먼저 오게 한다.- 노드 번호는 0부터 다루고, 적을 때
v + 1로 1부터로 바꾼다.
6단계 · 실행 추적
nodeinfo = [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]
넣는 순서는 7, 4, 2, 6, 1, 3, 9, 8, 5다(위층부터, 같은 층은 x 순).
| 넣는 노드 (x) | 내려간 길 | 자리 |
|---|---|---|
| 7 (8) | 뿌리 | |
| 4 (3) | 7 | 7의 왼쪽 |
| 2 (11) | 7 | 7의 오른쪽 |
| 6 (1) | 7 → 4 | 4의 왼쪽 |
| 1 (5) | 7 → 4 | 4의 오른쪽 |
| 3 (13) | 7 → 2 | 2의 오른쪽 |
| 9 (2) | 7 → 4 → 6 | 6의 오른쪽 |
| 8 (7) | 7 → 4 → 1 | 1의 오른쪽 |
| 5 (6) | 7 → 4 → 1 → 8 | 8의 왼쪽 |
전위는 7, 4, 6, 9, 1, 8, 5, 2, 3이고, 후위는 9, 6, 5, 8, 1, 4, 3, 2, 7이다.
7단계 · 복잡도와 흔한 실수
정렬 \(O(n \log n)\), 넣기는 노드마다 깊이만큼이라 최악 \(O(n \cdot h)\)(h ≤ 1,000), 순회 \(O(n)\)이다. 노드 1만 개로 재 보니 0.1초가 안 걸렸다.
- 재귀로 순회하며 재귀 한도를 늘리지 않아
RecursionError가 난다(깊이 1,000). - 노드를 입력 순서대로 넣어 부모보다 자식이 먼저 들어간다. 반드시 위층부터 넣는다.
- 결과에 0부터 센 번호를 그대로 적는다.
-
프로그래머스 스쿨, “길 찾기 게임” (https://school.programmers.co.kr/learn/courses/30/lessons/42892), 2026-09-30 조회. ↩
-
넣은 개수에 대한 귀납법으로 보인다. 지금까지 넣은 노드로 된 트리가 목표 트리를 그 노드들만 남겨 줄인 것과 같다고 하자. 새 노드 v의 조상은 모두 이미 들어가 있다. 목표 트리가 x를 열쇠로 한 이진 탐색 트리라서, v는 뿌리부터 갈림길마다 목표 트리에서와 같은 쪽으로 가며 자기 조상들을 차례로 지난다. 부모 아래 v 쪽 자리는 목표 트리에서 v 자신의 자리라 아직 비어 있으니, v는 목표 트리의 자리에 들어간다. ↩