[BOJ 11279] 최대합 (nodejs)

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

어려운 문제는 아닌데 삽질을 너무 많이했다...

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

class MaxHeap {
  constructor() {
    this.heap = [0];
  }

  // 삭제과정에서 부모가 자식보다 작은 경우 교체
  isSmallerThanChildren(idx) {
    let leftChildIdx = 2 * idx;
    let rightChildIdx = 2 * idx + 1;
  
    // 왼쪽 자식과 오른쪽 자식 노드가 모두 존재하는지 확인
    if (rightChildIdx < this.heap.length) {
      return (
        this.heap[idx] < this.heap[leftChildIdx] ||
        this.heap[idx] < this.heap[rightChildIdx]
      );
    } else if (leftChildIdx < this.heap.length) { // 왼쪽 자식만 존재하는 경우
      return this.heap[idx] < this.heap[leftChildIdx];
    } 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);
    }
  }

  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.isSmallerThanChildren(currentIdx)) {
        if (this.heap[2 * currentIdx + 1] > this.heap[2 * currentIdx]) {
          // 왼쪽 오른쪽 둘다 존재하는 경우
            this.swapValue(2 * currentIdx + 1, currentIdx);
            currentIdx = 2 * currentIdx + 1;
          }
         else {
          // 왼쪽만 존재하는 경우
            this.swapValue(2 * currentIdx, currentIdx);
            currentIdx = 2 * currentIdx;
          }
        
      }

      return removedVal;
    } else return 0;
  }
}

const pq = new MaxHeap();
const N = Number(input.shift());
const arr = input.map(Number);

const answer = [];
for (let i = 0; i < N; i++) {
  if (arr[i] > 0) {
    pq.insert(arr[i]);
  } else {
    answer.push(pq.remove());
  }
}
console.log(answer.join("\n"));

1. 이전에 작성한 최소힙 코드에서 부호만 바꿔주면 되는줄 알았는데 요소를 삭제하고 왼쪽 자식과 오른쪽 자식을 탐색할 때 힙의 사이즈를 벗어나는 경우가 있으므로 항상 자식 인덱스가 힙의 사이즈보다 작을때만 조건문을 탐색하도록 하였다.

2. 이전 코드에서 왼쪽 자식과 오른쪽 자식을 비교하는 로직이 있었는데 사실 애초에 삽입을 할때 최대힙에서는 왼쪽이 항상 크므로 비교하는 부분을 뺐다.

3. 왼쪽 자식부터 채워지므로 왼쪽 자식만 있는경우 / 왼쪽 오른쪽 자식 모두 있는 경우로 나눠서 생각하였다.

그러면 최소힙에서는 왜 오류가 안났을까? 단순히 운이 좋아서 이지 않을까..?