[Javascript] 프로그래머스 - 길 찾기 게임

문제 설명

라이언은 카카오 프렌즈와 함께 이진트리 탐색 게임을 구상했다. 주어진 2차원 좌표를 기반으로 특정 규칙에 따라 이진트리를 구성하고, 전위 순회(preorder)와 후위 순회(postorder) 결과를 반환하는 문제이다.

트리 구성 규칙

• 모든 노드는 서로 다른 x 값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 부모 노드의 y 값은 자식 노드보다 크다.
• 왼쪽 서브트리의 모든 노드의 x 값은 부모보다 작고, 오른쪽 서브트리의 모든 노드의 x 값은 부모보다 크다.

---

제한 사항

• nodeinfo의 길이는 1 ≤ N ≤ 10,000
• nodeinfo[i] = [x, y] (각 노드의 좌표)
• 모든 좌표 값은 0 ≤ x, y ≤ 100,000
• 트리의 깊이는 1,000 이하

---

해결 방법

알고리즘: 이진트리 구성 및 순회 (Binary Tree Construction & Traversal)

1. 노드 정렬
   • y 값 기준으로 내림차순 정렬하여 트리의 루트부터 차례로 삽입할 수 있도록 한다.
2. 이진트리 구성
   • 첫 번째 노드를 루트로 설정하고, 이후 노드를 이진트리 삽입 규칙에 맞춰 추가한다.
   • 왼쪽 서브트리는 x 값이 부모보다 작은 노드로, 오른쪽 서브트리는 x 값이 부모보다 큰 노드로 구성한다.
3. 트리 순회
   • 전위 순회 (Preorder): 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
   • 후위 순회 (Postorder): 왼쪽 서브트리 → 오른쪽 서브트리 → 루트

---

시간 복잡도

• 트리 구성: O(N log N)
  • 정렬 O(N log N), 트리 삽입 O(log N) × N 개 노드
• 순회: O(N)
• 총 시간 복잡도: O(N log N)

---

구현 코드

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function insertNode(parent, node, xMap) {
  if (xMap[node.value] < xMap[parent.value]) {
    if (!parent.left) parent.left = node;
    else insertNode(parent.left, node, xMap);
  } else {
    if (!parent.right) parent.right = node;
    else insertNode(parent.right, node, xMap);
  }
}

function preorder(node, pre) {
  if (!node) return;
  pre.push(node.value);
  preorder(node.left, pre);
  preorder(node.right, pre);
}

function postorder(node, post) {
  if (!node) return;
  postorder(node.left, post);
  postorder(node.right, post);
  post.push(node.value);
}

function solution(nodeinfo) {
  let nodes = nodeinfo.map((item, idx) => [...item, idx + 1]);
  nodes.sort((a, b) => b[1] - a[1]);

  let xMap = {};
  nodes.forEach(([x, y, num]) => (xMap[num] = x));

  let root = new TreeNode(nodes[0][2]);

  for (let i = 1; i < nodes.length; i++) {
    let node = new TreeNode(nodes[i][2]);
    insertNode(root, node, xMap);
  }

  let pre = [];
  let post = [];

  preorder(root, pre);
  postorder(root, post);

  return [pre, post];
}