문제 요약
각 노드는 서로 다른 x 좌표와 y 좌표를 가진다.
트리는 다음 조건을 만족해야 한다.
- 부모의
y좌표는 자식의y좌표보다 크다. - 왼쪽 서브트리의 모든
x좌표는 부모보다 작다. - 오른쪽 서브트리의 모든
x좌표는 부모보다 크다.
주어진 좌표로 이진트리를 구성한 뒤, 전위 순회와 후위 순회 결과를 반환해야 한다.
핵심 아이디어
이 트리는 두 가지 성질을 동시에 가진다.
x좌표 기준으로는 이진 탐색 트리(BST)다.y좌표 기준으로는 부모가 자식보다 큰 최대 힙이다.
이 두 성질을 함께 만족하는 트리를 카테시안 트리(Cartesian Tree)로 구성할 수 있다.
x 좌표 오름차순으로 노드를 처리하면서 y 좌표가 감소하는 단조 스택을 유지하면 트리를 효율적으로 만들 수 있다.
카테시안 트리 구성 원리
노드를 x 좌표 기준으로 정렬한다.
x가 작은 노드 → x가 큰 노드 순서정렬된 순서에서 현재 노드보다 y가 작은 노드는 현재 노드의 왼쪽 서브트리에 속할 수 있다. 따라서 스택에서 현재 노드보다 y가 작은 노드를 모두 꺼낸다.
while stack and stack[-1][1] < y:
last = stack.pop()꺼낸 마지막 노드는 현재 노드의 왼쪽 자식이 된다.
left[current] = last스택에 남아 있는 노드가 있다면, 그 노드는 현재 노드보다 x가 작고 y가 크다. 따라서 현재 노드는 그 노드의 오른쪽 자식이 된다.
right[stack[-1]] = current왜 단조 스택을 사용하는가
단순하게 y 좌표 내림차순으로 노드를 정렬한 뒤 하나씩 BST에 삽입할 수도 있다.
하지만 트리가 한쪽으로 치우친 경우 삽입마다 많은 노드를 탐색하게 되어 최악의 경우 O(N^2)이 될 수 있다.
단조 스택 방식에서는 각 노드가 스택에 한 번 들어가고 한 번만 나간다. 따라서 트리 구성은 정렬 이후 O(N)에 끝난다.
Python 코드
def solution(nodeinfo):
n = len(nodeinfo)
# (x 좌표, y 좌표, 노드 번호) 형태로 저장 후 x 기준 정렬
nodes = sorted(
(x, y, index + 1)
for index, (x, y) in enumerate(nodeinfo)
)
left = [0] * (n + 1)
right = [0] * (n + 1)
stack = []
# x 오름차순 + y 내림차순 단조 스택으로 카테시안 트리 구성
for x, y, node_id in nodes:
last = 0
# 현재 노드보다 y가 작은 노드는 현재 노드의 왼쪽 서브트리 후보
while stack and stack[-1][1] < y:
last = stack.pop()[2]
# 가장 마지막에 빠진 노드가 현재 노드의 왼쪽 자식
if last:
left[node_id] = last
# 스택 top은 현재 노드의 부모가 되고, 현재 노드는 오른쪽 자식
if stack:
parent_id = stack[-1][2]
right[parent_id] = node_id
stack.append((x, y, node_id))
# 스택의 가장 아래 노드는 전체 트리의 루트
root = stack[0][2]
# 전위 순회: 루트 -> 왼쪽 -> 오른쪽
preorder = []
traversal_stack = [root]
while traversal_stack:
node_id = traversal_stack.pop()
preorder.append(node_id)
# 스택은 나중에 넣은 노드가 먼저 나오므로 오른쪽을 먼저 넣는다.
if right[node_id]:
traversal_stack.append(right[node_id])
if left[node_id]:
traversal_stack.append(left[node_id])
# 후위 순회: 왼쪽 -> 오른쪽 -> 루트
# 루트 -> 오른쪽 -> 왼쪽 순서로 모은 뒤 뒤집는다.
reverse_postorder = []
traversal_stack = [root]
while traversal_stack:
node_id = traversal_stack.pop()
reverse_postorder.append(node_id)
if left[node_id]:
traversal_stack.append(left[node_id])
if right[node_id]:
traversal_stack.append(right[node_id])
postorder = reverse_postorder[::-1]
return [preorder, postorder]코드 설명
x 좌표 기준 정렬
nodes = sorted(
(x, y, index + 1)
for index, (x, y) in enumerate(nodeinfo)
)모든 노드의 x 좌표는 서로 다르므로 x 오름차순 정렬 결과가 명확하다.
이 순서를 기준으로 만들면 왼쪽 자식은 항상 더 작은 x, 오른쪽 자식은 항상 더 큰 x를 가지게 된다.
왼쪽 자식 결정
while stack and stack[-1][1] < y:
last = stack.pop()[2]
if last:
left[node_id] = last현재 노드보다 y가 작은 노드를 스택에서 꺼낸다.
여러 노드가 꺼질 수 있지만, 가장 마지막에 꺼낸 노드는 현재 노드와 가장 가까운 부모-자식 관계를 형성하므로 현재 노드의 왼쪽 자식이 된다.
오른쪽 자식 결정
if stack:
parent_id = stack[-1][2]
right[parent_id] = node_id스택에 남아 있는 맨 위 노드는 현재 노드보다 x가 작고 y가 크다.
따라서 현재 노드는 해당 노드의 오른쪽 자식이 된다.
반복형 순회
노드 수가 많고 트리가 한쪽으로 치우칠 수 있으므로 재귀 대신 스택을 사용한다.
전위 순회에서는 오른쪽 -> 왼쪽 순서로 스택에 넣어, 꺼낼 때 왼쪽 -> 오른쪽 순서가 되게 한다.
후위 순회는 루트 -> 오른쪽 -> 왼쪽 순서로 저장한 뒤 역순으로 뒤집으면 왼쪽 -> 오른쪽 -> 루트 순서가 된다.
정확성
노드를 x 오름차순으로 처리하므로 현재 노드보다 먼저 처리된 모든 노드는 더 작은 x 좌표를 가진다. 현재 노드를 스택에 남아 있는 노드의 오른쪽 자식으로 연결하거나, 스택에서 꺼낸 노드를 현재 노드의 왼쪽 자식으로 연결하므로 이진 탐색 트리 조건을 만족한다.
현재 노드보다 작은 y 좌표를 가진 노드는 스택에서 제거되고, 스택에 남아 있는 부모 후보는 현재 노드보다 큰 y 좌표를 가진다. 따라서 모든 부모의 y 좌표가 자식보다 큰 조건도 만족한다.
카테시안 트리 구성 과정은 각 노드의 좌우 자식 관계를 정확히 한 번 결정한다. 이후 전위 순회와 후위 순회는 각각 정의에 맞는 스택 순서로 자식을 방문하므로 반환된 두 배열은 문제에서 요구한 순회 결과다.
시간 복잡도
노드 수를 N이라고 하자.
x좌표 정렬:O(N log N)- 단조 스택 트리 구성:
O(N) - 전위·후위 순회:
O(N)
전체 시간 복잡도는 다음과 같다.
O(N log N)공간 복잡도
노드 정보, 좌우 자식 배열, 스택, 순회 결과를 저장한다.
O(N)주의할 점
- 노드 번호는
nodeinfo의 입력 순서에 따라1부터 시작한다. x좌표는 모두 다르므로x기준 정렬만으로 이진 탐색 트리 순서를 만들 수 있다.- 전위 순회에서 오른쪽 자식을 먼저 스택에 넣어야 왼쪽 자식이 먼저 방문된다.
- 후위 순회를 재귀로 구현하면 편하지만, 편향 트리에서는 재귀 깊이 문제가 생길 수 있다.
- 이 문제의 좌표 조건을 만족하는 입력에서는 같은
y좌표의 노드가 부모-자식 관계가 되지 않는다.
정리
이 문제는 좌표를 이용해 BST 조건과 최대 힙 조건을 동시에 만족하는 이진트리를 만드는 문제다.
x 좌표 정렬과 y 좌표 단조 스택으로 카테시안 트리를 구성하면 트리 생성과 두 순회를 모두 효율적으로 처리할 수 있다.
