백준 9934 완전 이진트리 node.js

 

접근법을 알면 쉽게 풀 수 있지만, 당연히도 접근법 생각하는 게 쉽지 않았던 문제이다.

입력으로 주어지는 배열은 트리를 중위순회한 값이라는 걸 알 수 있다. 이것이 매우 중요하다.

중위순회임임을 통해서 적절한 부분 배열로 나누었을 때 (자식 노드) - (부모 노드) - (자식 노드) 의  패턴이 유지된다는 것을 유추해야 한다. 여기가 어렵다.

 

입력의 인덱스 중앙값은 항상 트리의 루트 노드이다 즉 전체 배열 기준으로 양 부분 배열 사이의 노드가 부모 노드라는 뜻이다.

그리고 부모 노드 기준으로 양쪽 부분배열로 나누었을 때, 그 부분 배열 또한 부모 노드와 자식 노드를 포함하는 서브 트리임을 알 수 있다.

큰 문제를 같은 패턴의 작은 문제로 나눌 수 있고, 서로 독립적이다. 그러므로 재귀를 이용한 풀이를 생각해낼 수 있다.

 

부모 노드는 항상 부분 배열의 중앙으로 확정이기 때문에, 부모 노드를 해당 높이의 트리(배열)에 넣은 후 이후 부모 노드 기준으로 다시 양쪽 배열로 분할한 후 재귀 함수를 호출한다.

let readline = require("readline");

let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

let input = [];

rl.on("line", (line)=> {
	input.push(line);
}).on("close", () => {

	const k = Number(input[0]);
	const arr = input[1].split(' ').map(Number);

	const ans = Array(k+1);
	for(let i = 0; i <= k; i++)
		ans[i] = '';


	const make = (arr, depth) => {

		if(depth > k || arr.length === 0)
			return;

		const mid = Math.floor(arr.length / 2);
		if(ans[depth].length === 0)
			ans[depth] += arr[mid].toString();
		else
		ans[depth] += ' ' + arr[mid].toString();
		const leftarr = arr.slice(0, mid);
		const rightarr = arr.slice(mid+1, arr.length);

		make(leftarr, depth + 1);
		make(rightarr, depth + 1);
	}

	make(arr, 1);

	console.log(ans.slice(1,ans.length).join('\n'))
})