[백준] 11279번: 최대 힙 - Node.js (자바스크립트)

1. 문제 ㅡ 11279번: 최대 힙 (난이도: Silver II)

11279번: 최대 힙

2. 풀이 ㅡ Node.js (자바스크립트)

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

  isEmpty() {
    return this.heap.length === 0;
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let currentIndex = this.heap.length - 1;

    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);

      if (this.heap[parentIndex] >= this.heap[currentIndex]) break;

      [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]];
      currentIndex = parentIndex;
    }
  }

  getMax() {
    if (this.heap.length == 1) return this.heap.pop();
    if (!this.heap.length) return 0;

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);

    return max;
  }

  sinkDown(index) {
    const leftIndex = 2 * index + 1;
    const rightIndex = 2 * index + 2;
    const length = this.heap.length;
    let largestIndex = index;

    if (leftIndex < length && this.heap[leftIndex] > this.heap[largestIndex]) {
      largestIndex = leftIndex;
    }

    if (rightIndex < length && this.heap[rightIndex] > this.heap[largestIndex]) {
      largestIndex = rightIndex;
    }

    if (largestIndex !== index) {
      [this.heap[index], this.heap[largestIndex]] = [this.heap[largestIndex], this.heap[index]][
        (this.heap[index], this.heap[largestIndex])
      ] = [this.heap[largestIndex], this.heap[index]];
      this.sinkDown(largestIndex);
    }
  }
}

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

const solution = () => {
  const answer = [];
  const maximumHeap = new MaxHeap();

  for (let i = 0; i < +N; i++) {
    +input[i] === 0 ? answer.push(maximumHeap.getMax()) : maximumHeap.insert(+input[i]);
  }

  return answer.join('\n');
};

console.log(solution());

 

2-1. 풀이 설명

모든 낮은 난이도의 자료구조 유형 문제들이 그렇듯, 클래스로 자료구조를 직접 구현하고 문제 풀이에 접근하는 것이 핵심인 문제다. MaxHeap 클래스를 구현한 후 새로운 인스턴스를 생성했다. 이후 입력을 반복문으로 돌면서 0인 경우, 현재 힙에 값이 들어있으면 가장 큰 숫자를, 값이 없으면 0을 반환해주는 getMax 메서드를 호출해서 answer 배열에 순서대로 담아줬다. 반대로 순회 중인 입력값이 0 외의 값인 경우에는 힙에 담아주고, 힙을 재정렬하여 최댓 값을 찾기 쉽게 해뒀다.