문제 번호 : 1715 번 문제 바로가기 ☞ https://www.acmicpc.net/problem/1715
<<< 문제 내용 >>>
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().split("\r\n");
let heap = [null];
const swap = (a, b) => {
[heap[a], heap[b]] = [heap[b], heap[a]];
};
const heappush = (value) => {
heap.push(value);
let curIdx = heap.length - 1;
let parIdx = (curIdx / 2) >> 0;
while (curIdx > 1 && heap[curIdx] < heap[parIdx]) {
swap(curIdx, parIdx);
curIdx = parIdx;
parIdx = (curIdx / 2) >> 0;
}
};
const heappop = () => {
const min = heap[1];
if (heap.length <= 2) heap = [null];
else heap[1] = heap.pop();
let [curIdx, leftIdx, rightIdx] = [1, 2, 3];
if (!heap[leftIdx]) return min;
if (!heap[rightIdx]) {
if (heap[curIdx] > heap[leftIdx]) swap(curIdx, leftIdx);
return min;
}
while (heap[curIdx] > heap[leftIdx] || heap[curIdx] > heap[rightIdx]) {
const minIdx = heap[leftIdx] > heap[rightIdx] ? rightIdx : leftIdx;
swap(minIdx, curIdx);
curIdx = minIdx;
leftIdx = curIdx * 2;
rightIdx = curIdx * 2 + 1;
}
return min;
};
const N = Number(input[0]);
let sumAmount = 0;
for (let i = 1; i < N + 1; i++) {
heappush(Number(input[i]));
}
while (heap.length > 2) {
const amount = heappop() + heappop();
heappush(amount);
sumAmount += amount;
}
console.log(sumAmount);
* 최소힙을 구현해 놓고 모든 수를 heap에 넣어줍니다.
이 후 heappop을 두번하고 리턴되는 수를 amount에 저장하여 heap에 다시 넣어주고 비교횟수도 알아야하니 sumAmount에 누적해서 값을 저장해주면 끝
- 왜 더한 수를 다시 넣어줘야 하냐면 [10, 20, 20, 20, 30]이 있을 때 10+20 = 30이 되고 다시 넣으면 [20, 20, 30, 30]이 남는다. 그 다음으로 작게 비교하는 방법이 위에 비교했던 30을 다음 작은 수와 비교한다면 20 + 30 = 50인데, 이 보다 빠른 것은 [20, 20, 30, 30] 중에서 20 + 20 = 40 으로 비교하는게 더 최적화되기 때문이다.
도움이 되셨다면 공감 부탁드립니다.