백준9934 - 완전 이진 트리 (재귀, 이진트리) node.js

https://www.acmicpc.net/problem/9934

 

해당 문제는 입력값으로 깊이값 K와 순회한 이진트리 데이터를 주고, 이를 활용하여 각 노드마다 2개의 자식 노드를 갖는 완전이진트리를 구성하여 출력하는 문제다.

문제 풀이 방식

완전이진트리라는 특징을 이용하여 최정점에서부터 다음 깊이의 두 노드들을 파악해가는 방식으로 진행했다. 먼저 [1,6,4,3,5,2,7] 라는 데이터가 주어졌을 경우, 가장 깊이가 0인 최정점 노드는 해당 배열 가운데에 위치한 3 이다.

이후 다음 깊이가 1인 노드의 경우를 파악하는 방식은 단순한데, 최정점 노드가 위치한 3의 좌우에 위치한 배열들에서 가운데에 위치하는 것이 깊이 0 노드의 자식 노드들이 된다. (즉, [1,6,4] 에서의 6. [5,2,7]에서의 2가, 깊이가 0인 노드 3의 자식 노드이자, 깊이 1의 노드들인 셈이다.)

이후 이와 같은 방식으로 재귀 함수를 통해 각 노드들을 구해낼 수 있다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [[n], arr] = data.map((el) => el.split(" ").map(Number));
  const trees = Array.from({ length: n }, () => []);

  makingTree(arr, trees, 0);
  console.log(trees.map((el) => el.join(" ")).join("\n"));
}

function makingTree(list, trees, dep) {
  const mid = Math.floor(list.length / 2);
  trees[dep].push(list[mid]);

  if (list.length === 1) return; // 최하단 노드인 경우 종료
  else {
    makingTree(list.slice(0, mid), trees, dep + 1);
    makingTree(list.slice(mid + 1), trees, dep + 1);
  }
}

solution(input);