Node.js)백준 2233번: 사과나무

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

 

class Apple {
	constructor(pos1, parent) {
		this.position = [pos1];
		this.parent = parent;
		this.height = parent?.height ? parent.height + 1 : 1;
	}

	mark(pos2) {
		this.position.push(pos2);
	}
}

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');
const N = +input[0];
const binary = input[1].trim();
const [t1, t2] = input[2].split(' ').map(Number);
const answer = [];

const applePosition = new Array(2 * N + 1).fill(null);
const root = new Apple(1, null);
let now = root;
applePosition[1] = root;
for (let i = 1; i < binary.length; i++) {
	let pos = i + 1;
	if (binary[i] == '0') {
		const newNode = new Apple(pos, now);
		applePosition[pos] = newNode;
		now = newNode;
	} else {
		applePosition[pos] = now;
		now.mark(pos);
		now = now.parent;
	}
}
let A = applePosition[t1];
let B = applePosition[t2];
while (A.height > B.height) {
	A = A.parent;
}
while (B.height > A.height) {
	B = B.parent;
}

while (A.position[0] != B.position[0]) {
	A = A.parent;
	B = B.parent;
}
console.log(A.position.join(' '));