백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 9934 , 완전 이진 트리

백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 9934 , 완전 이진 트리 [트리]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


덧붙일 말 🏷️
세그먼트 트리 풀 때, 익혀두었던 재귀로 풀었다. 트리 계층화 시키는 기본 문제다.

 

 

문제 출처 🏠

 

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

9934번: 완전 이진 트리

 

 

 

요구사항 📋

첫째줄에, K가 주어지는데 1 이상 2^K 미만의 구간을 나타냄.
둘째줄에는 2^K-1 만큼의 숫자가 주어짐. 이는 트리 왼쪽부터의 순서다.

트리를 계층화하여, 0번 계층부터 K-1 계층 순서대로 출력하여라.

 

 

 

 

해결 전략 📝

 

둘째 줄에 주어지는 숫자들은 트리를 계층화 시켰을 때, 왼쪽 순서대로 주어진다.

이 점을 이용해서 mid 값을 줄여나가는 재귀를 진행한다.

 

mid 인덱스를 기준으로 왼쪽 오른쪽을 나눠서 재귀를 해주고 파라미터 값으로는 구간을 쪼갠 배열과 현재의 계층을 담은 변수를 전달한다.

 

 

최종적으로, 쪼갠 배열의 길이가 1개가 되면 리프노드에 도착한 것이므로 return 시킨다.

 

완전 이진 트리이기 때문에, 가능한 풀이이다.

 

 

 

 

 

 

정답 💯

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let [K, ...NUMS] = input;

NUMS = NUMS[0].split(" ").map(Number);
function solution(k, Nodes) {
  let tree = Array.from({ length: k + 1 }).map(() => []);

  const makeTree = (nodes, layer) => {
    let mid = ~~(nodes.length / 2);
    tree[layer].push(nodes[mid]);
    if (nodes.length === 1) return;
    if (layer + 1 <= k) {
      makeTree(nodes.slice(0, mid), layer + 1);
      makeTree(nodes.slice(mid, nodes.length), layer + 1);
    }
  };

  makeTree(Nodes, 1);
  for (let i = 1; i <= k; i++) console.log(tree[i].join(" "));
}

solution(Number(K), NUMS);

 

 

느낀점 🧑‍💻

트리 기본 문제로 좋은 문제 같다. 재귀탐색을 하면서 트리를 계층화시키는 과정이 재밌었음.