[BOJ 15903] 카드 합체 놀이 알고리즘(nodejs)

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");


class MinHeap {// idx = 1에 min value 저장
    constructor() {
      this.heap = [BigInt(0)];
    }
  
  // 삭제과정에서 부모가 자식보다 큰 경우 교체
  isBiggerThanChildren(idx) {
    // 자식이 존재하는지
    if (this.heap[2 * idx]) {
            return (
                this.heap[idx] > this.heap[2 * idx] ||
                this.heap[idx] > this.heap[2 * idx + 1]
            );
        } 
  
    else {
        return false;
    }
}

  
    swapValue(idx1, idx2) {
      [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
    }
  
    insert(value) {
      this.heap.push(value);
  
      let currentIdx = this.heap.length - 1;
      let parentIdx = Math.floor(currentIdx / 2);
  
      while (currentIdx > 1 && this.heap[currentIdx] < this.heap[parentIdx]) {
        this.swapValue(currentIdx, parentIdx);
        currentIdx = parentIdx;
        parentIdx = Math.floor(currentIdx / 2);
      }
    }

    sum(){
        return this.heap.reduce((a, b) => a+b, BigInt(0));
    }
  
    remove() {
    // 최소 하나는 있는 경우 [0, value]인 경우
      if (this.heap.length > 1) {
      // [0, value] 인 경우 value 리턴
        if (this.heap.length === 2) return this.heap.pop();
  
        let removedVal = this.heap[1];
        this.heap[1] = this.heap.pop();
        let currentIdx = 1;
  
        // 우선 자식들이 부모보다 작은 경우
        while (this.isBiggerThanChildren(currentIdx)) {
            if ( this.heap[2 * currentIdx + 1] < this.heap[2 * currentIdx]) {
                // 오른쪽 자식이 존재하고, 오른쪽 자식이 왼쪽 자식보다 작은 경우
                if (this.heap[2 * currentIdx + 1] < this.heap[currentIdx]) {
                    this.swapValue(2 * currentIdx + 1, currentIdx);
                    currentIdx = 2 * currentIdx + 1;
                }
            } else {
                // 왼쪽 자식이 부모보다 작은 경우
                if (this.heap[2 * currentIdx] < this.heap[currentIdx]) {
                    this.swapValue(2 * currentIdx, currentIdx);
                    currentIdx = 2 * currentIdx;
                }
            }
        }
  
        return removedVal;
      } else return null;
    }
  }
  
let [N, M] = input.shift().split(' ').map(Number)
let arr = input.shift().split(' ').map(BigInt);
let pq = new MinHeap();

for(let i=0; i<arr.length; i++){
    pq.insert(BigInt(arr[i]))
}

while(M > 0){
    let first = pq.remove();
    let second = pq.remove();
    pq.insert(first+second);
    pq.insert(first+second);
    M--;
}
console.log(pq.sum().toString());

구글에 문제 정보가 적어서 백준에서 다른 사람 코드를 참고하였다.
nodejs로 깔끔하게 풀기 어려운 문제다.
다른 언어들은 라이브러리를 통해 풀거나, 굳이 우선순위 큐를 사용하지않고 매번 sort해도 풀리는 것 같은데 js는 속도도 느리고, 라이브러리를 제공하지 않아서 우선순위 큐를 직접 라이브러리로 구현해야 한다.
사실 우선순위 큐를 잘 몰라서 덕분에 공부할 수 있었다.

게다가 카드의 개수 n이 2~1000이고, 카드의 값이 1~1,000,000 이므로 js에서 제공하는 Number만으로 문제를 해결할 수 없으므로 BigInt를 초기값과 삽입, sorting할때도 지정해야 한다는 점 때문에 정보가 많이 없는 것 같다.