Node.js) 백준 13975번: 파일합치기 3

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

13975번: 파일 합치기 3

class PriorityQueue {
	constructor(priority) {
		this.heap = [];
		this.pairIsInCorrectOrder = priority;
	}

	getLeftChildIndex(parentIndex) {
		return 2 * parentIndex + 1;
	}

	getRightChildIndex(parentIndex) {
		return 2 * parentIndex + 2;
	}

	getParentIndex(childIndex) {
		return Math.floor((childIndex - 1) / 2);
	}

	hasParent(childIndex) {
		return this.getParentIndex(childIndex) >= 0;
	}

	hasLeftChild(parentIndex) {
		return this.getLeftChildIndex(parentIndex) < this.heap.length;
	}

	hasRightChild(parentIndex) {
		return this.getRightChildIndex(parentIndex) < this.heap.length;
	}

	leftChild(parentIndex) {
		return this.heap[this.getLeftChildIndex(parentIndex)];
	}

	rightChild(parentIndex) {
		return this.heap[this.getRightChildIndex(parentIndex)];
	}

	parent(childIndex) {
		return this.heap[this.getParentIndex(childIndex)];
	}

	swap(indexA, indexB) {
		const tmp = this.heap[indexA];
		this.heap[indexA] = this.heap[indexB];
		this.heap[indexB] = tmp;
	}

	peek() {
		return this.heap.length == 0 ? null : this.heap[0];
	}

	isEmpty() {
		return !this.heap.length;
	}

	pop() {
		if (this.heap.length == 0) {
			return null;
		}

		if (this.heap.length == 1) {
			return this.heap.pop();
		}

		const item = this.heap[0];

		this.heap[0] = this.heap.pop();
		this.bubbleDown();
		return item;
	}

	push(item) {
		this.heap.push(item);
		this.bubbleUp();
		return this;
	}

	bubbleUp() {
		let currentIndex = this.heap.length - 1;

		while (
			this.hasParent(currentIndex) &&
			!this.pairIsInCorrectOrder(this.parent(currentIndex), this.heap[currentIndex])
		) {
			this.swap(currentIndex, this.getParentIndex(currentIndex));
			currentIndex = this.getParentIndex(currentIndex);
		}
	}

	bubbleDown() {
		let currentIndex = 0;
		let nextIndex = null;

		while (this.hasLeftChild(currentIndex)) {
			if (
				this.hasRightChild(currentIndex) &&
				this.pairIsInCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))
			) {
				nextIndex = this.getRightChildIndex(currentIndex);
			} else {
				nextIndex = this.getLeftChildIndex(currentIndex);
			}
			if (this.pairIsInCorrectOrder(this.heap[currentIndex], this.heap[nextIndex])) {
				break;
			}
			this.swap(currentIndex, nextIndex);
			currentIndex = nextIndex;
		}
	}

	findOne(target) {
		for (let i = 0; i < this.heap.length; i++) {
			if (this.heap[i] == target) {
				return i;
			}
		}
		return -1;
	}

	removeOne(target) {
		const indexToRemove = this.findOne(target);
		if (indexToRemove == -1) return;
		if (indexToRemove == this.heap.length - 1) {
			this.heap.pop();
		} else {
			this.heap[indexToRemove] = this.heap.pop();
			const parentItem = this.parent(indexToRemove);
			if (
				this.hasLeftChild(indexToRemove) &&
				(!parentItem || this.pairIsInCorrectOrder(parentItem, this.heap[indexToRemove]))
			) {
				this.bubbleDown(indexToRemove);
			} else {
				this.bubbleUp(indexToRemove);
			}
		}
	}
}

const priority = (a, b) => {
	if (a < b) return true;
	else false;
};

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');
const T = input[0];

for (let t = 0; t < T; t++) {
	const pq = new PriorityQueue(priority);
	const fileList = input[2 * (t + 1)].split(' ');
	fileList.forEach((file) => {
		pq.push(+file);
	});
	let cost = 0;
	while (pq.heap.length > 1) {
		const newFile = pq.pop() + pq.pop();
		cost += newFile;
		pq.push(newFile);
	}
	console.log(cost);
}