🎲 백준 15903번 카드 합체 놀이

백준 15903번

🧸쉬운 문제라고 생각했는데.. 처음에는 sort를 사용해서 간단하게 풀었다. 하지만 틀렸다고 해서 찾아보았더니 두가지 주의할 점이 있었다.
💊 BigInt를 써야한다.
💊 우선순위 큐를 구현해야한다 : 나는 힙을 사용해 구현하였다.
🎨 heap 구현 참고 코드

코드

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

const [n, m] = input.shift().split(" ").map(Number);
const arr = input[0]
  .split(" ")
  .sort((a, b) => a - b)
  .map(BigInt);

 
class Heap {
  constructor() {
    this.heap = [...arr];
  }

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  peek = () => this.heap[0];

  //삽입
  insert = (value) => {
    const node = value;
    //배열의 끝에 넣고
    this.heap.push(node);
    //끌어올리기
    this.heapifyUp();
  };

  heapifyUp = () => {
    let index = this.heap.length - 1;
    const lastInsertedNode = this.heap[index];

    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      if (this.heap[parentIndex] > lastInsertedNode) {
        this.heap[index] = this.heap[parentIndex];
        index = parentIndex;
      } else break;
    }

    this.heap[index] = lastInsertedNode;
  };

  //제거
  remove = () => {
    const count = this.heap.length;
    const rootNode = this.heap[0];

    if (count <= 0) return undefined;
    if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    return rootNode;
  };

  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const rootNode = this.heap[index];

    //left child가 있을 때 까지
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex] < this.heap[leftChildIndex]
          ? rightChildIndex
          : leftChildIndex;

      if (this.heap[smallerChildIndex] <= rootNode) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }

    this.heap[index] = rootNode;
  };
}

const heap = new Heap();

for (let i = 0; i < m; i++) {
  const first = heap.heap[0];
  heap.remove();
  const second = heap.heap[0];
  heap.remove();

  const sum = first + second;
  heap.insert(sum);
  heap.insert(sum);
}

console.log(heap.heap.reduce((a, b) => a + b, 0n).toString());