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

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

1927번: 최소 힙

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

class MinimumHeap {
  constructor() {
    this.heap = [-Infinity];
  }

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

  bubbleUp(position) {
    let tmp = this.heap[position];

    while (tmp < this.heap[parseInt(position / 2)]) {
      this.heap[position] = this.heap[parseInt(position / 2)];
      position = parseInt(position / 2);
    }

    this.heap[position] = tmp;
  }

  get() {
    if (this.heap.length === 2) return this.heap.pop();

    let getResult = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.bubbleDown(1, this.heap.length - 1);
    return getResult;
  }

  bubbleDown(position, len) {
    let tmp = this.heap[position],
      child;

    while (position <= parseInt(len / 2)) {
      child = position * 2;

      if (child < len && this.heap[child] > this.heap[child + 1]) child += 1;
      if (tmp <= this.heap[child]) break;

      this.heap[position] = this.heap[child];
      position = child;
    }

    this.heap[position] = tmp;
  }

  size() {
    return this.heap.length - 1;
  }

  front() {
    return this.heap[1];
  }
}

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

const getMinimums = () => {
  const nums = input.map(val => +val);

  const minHeap = new MinimumHeap();
  let answer = '';

  nums.forEach(num => {
    if (num === 0) {
      if (!minHeap.size()) {
        answer += '0' + '\n';
      } else {
        answer += `${minHeap.front()}\n`;
        minHeap.get();
      }
    } else {
      minHeap.insert(num);
    }
  });

  return answer.trim();
};

console.log(getMinimums());

 

2-1. 풀이 설명

원래 백준에서 자료구조 유형 문제를 자바스크립트로 의식의 흐름대로 풀다 보면 시간 초과나는 경우가 대부분인데, 이번 문제에서는 아예 시간 제한이 '1초 (추가 시간 없음)'이라고 써져있는게 시간 초과 조심하라고 못을 박아주는 느낌이라 클래스로 직접 자료구조를 구현해서 풀이하는 것이 좋겠다고 생각했다. 

 

힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구다 (문제 이름에서 알 수 있듯 문제의 핵심은 최솟 값을 빠르게 찾아낼 수 있는 최소 힙을 구현하는 것). 이후 입력 값을 순회하면서 0이 나올 때마다 최솟값을 찾아오면 된다. 최소 힙을 구현하는 방법은 다양하겠지만, 헷갈린다면 다른 분들이 짜둔걸 몇 개 읽어보고 스스로 구현해보면 좋은 연습이 될 것 같다 (나 또한 그렇게 했다).