[BaekJoon] 1715 번 카드 정렬하기 문제 - (nodejs)

문제 번호 :  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 으로 비교하는게 더 최적화되기 때문이다.

 

도움이 되셨다면 공감 부탁드립니다.