문제 링크

풀이 과정

• 본 문제는 이진 트리를 조건에 맞게 구현하는 것이 핵심입니다. 개인적으로, 이진 트리를 직접 구현한 경험이 없어서 문제를 푸는 데 많이 애를 먹었습니다…..
• 트리를 구현할 때는 크게 두 가지 사항을 고려해야 합니다.
  • 트리를 구성하는 노드를 어떻게 정의할 것인가? 즉, 노드에 어떤 데이터를 저장할 것인가?
  • 트리 내에서, 노드 분기(branch) 기준은 무엇으로 할 것인가?
• 문제 조건에 따르면, 모든 노드의 x 좌표 값은 서로 다르다고 하였습니다.
  • 따라서, 노드 분기 기준은 노드의 x 좌표 값을 이용합니다.
  • 새로운 노드의 x 좌표 값이 현재 노드의 x 좌표 값보다 작은 경우 → 새로운 노드는 현재 노드의 왼쪽 서브트리에 위치
  • 새로운 노드의 x 좌표 값이 현재 노드의 x 좌표 값보다 큰 경우 → 새로운 노드는 현재 노드의 오른쪽 서브트리에 위치
• 기준을 점검하기 위하여, 각 노드는 좌표 데이터를 가져야합니다!
• 결과적으로, 다음과 같이 정리할 수 있습니다!
  • 노드에 어떤 데이터를 저장할 것인가? → 왼쪽 자식 노드, 오른쪽 자식 노드, 좌표
  • 노드 분기(branch) 기준은 무엇으로 할 것인가? → x 좌표

결과적으로, 의사 코드는 아래와 같이 작성할 수 있습니다.

<Solution>
노드 번호를 좌표 값에 따라 정렬한다.
- (1순위) y 좌표: 큰 값 -> 작은 값
- (2순위) x 좌표: 작은 값 -> 큰 값

정렬된 노드 번호 순으로 이진 트리를 생성한다.

생성된 이진 트리를 통해 각각 전위 순회 및 후위 순회를 수행한다.

전체 코드

import sys
sys.setrecursionlimit(10 ** 6)

class Node:
    def __init__(
        self,
        node_num: int,
        coords: list,
        left = None,
        right = None
    ):
        self.node_num = node_num
        self.coords = coords
        self.left = left
        self.right = right
        
    def has_left(self):
        return self.left
    
    def has_right(self):
        return self.right
    
def make_binary_tree(nodeinfo: list) -> Node:
    # 노드 번호를 정렬 -> (y 좌표가 큰 순서 + x 좌표가 작은 순서)
    node_nums = [idx+1 for idx in range(len(nodeinfo))]
    node_nums = sorted(
        node_nums, 
        key=lambda x: (-nodeinfo[x-1][1], nodeinfo[x-1][0])
    )
    # 이진 트리 구성
    root = None
    for node_num in node_nums:
        if not root:
            root = Node(node_num, nodeinfo[node_num-1])
        else:
            # 분기는 항상 루트 노드에서 시작합니다!
            parent = root
            cur_node = Node(node_num, nodeinfo[node_num-1])
            while True:
                if parent.coords[0] > cur_node.coords[0]:  # x 좌표 비교
                    if parent.has_left():
                        parent = parent.left
                        continue
                    parent.left = cur_node
                    break
                else:
                    if parent.has_right():
                        parent = parent.right
                        continue
                    parent.right = cur_node
                    break
    return root

def pre_order(root: Node, routes: list):
    if root is None:    return

    routes.append(root.node_num)
    pre_order(root.left, routes)
    pre_order(root.right, routes)
    
def post_order(root: Node, routes: list):
    if root is None:    return
    
    post_order(root.left, routes)
    post_order(root.right, routes)
    routes.append(root.node_num)

def solution(nodeinfo):
    answer = [[], []]
    
    # 1. 트리 구성
    root = make_binary_tree(nodeinfo)
                    
    # 2. 전위 순회 실시
    pre_order(root, answer[0])
    
    # 3. 후위 순회 실시
    post_order(root, answer[1])
    
    return answer