Baekjoon 1927번 최소 힙

문제

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

걸린 시간

00 : 10 : 57

풀이

Python3

import sys
input = sys.stdin.readline

class minHeap():
    def __init__(self, max_size):
        self.heap = [None] * max_size
        self.heap_size = 0

    def is_empty(self):
        if self.heap_size == 0:
            return True
        else:
            return False

    def insert(self, item):
        self.heap_size += 1
        i = self.heap_size

        while i != 1 and self.heap[i//2] > item:
            self.heap[i] = self.heap[i//2]
            i = i//2

        self.heap[i] = item

    def delete(self):
        if self.is_empty():
            return 0
        else:
            item = self.heap[1]
            temp = self.heap[self.heap_size]
            self.heap_size -= 1

            parent = 1
            child = 2

            while child <= self.heap_size:
                if child < self.heap_size and self.heap[child] > self.heap[child+1]:
                    child += 1

                if self.heap[child] > temp:
                    break

                self.heap[parent] = self.heap[child]
                parent = child
                child *= 2

            self.heap[parent] = temp
            return item

if __name__ == "__main__":
    minH = minHeap(100000)
    result = []

    N = int(input().strip())

    for _ in range(0, N):
        tmp = int(input().strip())
        if tmp == 0:
            result.append(minH.delete())
        else:
            minH.insert(tmp)

    for i in result:
        print(i)

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

class Heap {
  constructor (compare = (a, b) => a < b) { // default : 최소 힙
    this.heap = [null];
    this.compare = compare;
  }
  insert(item) {
    this.heap.push(item);
    let i = this.heap.length-1;
    while(i !== 1 && this.compare(item, this.heap[Math.floor(i/2)])){
      this.heap[i] = this.heap[Math.floor(i/2)];
      i = Math.floor(i/2);
    }
    this.heap[i] = item;
  }
  delete() {
    const item = this.heap[1];
    const tmp = this.heap.pop();
    const len = this.heap.length-1;
    let parent = 1;
    let child = 2;
    while(child <= len){
      if(
        child < len &&
        this.compare(this.heap[child+1], this.heap[child])
      ){
        child += 1;
      }
      if(this.compare(tmp, this.heap[child])){
        break;
      }
      this.heap[parent] = this.heap[child];
      parent = child;
      child *= 2;
    }
    if(this.heap.length > 1) this.heap[parent] = tmp;
    return item;
  }
  empty() {
    return this.heap.length === 1;
  }
}

class PriorityQueue {
  constructor (compare) {
    this.heap = new Heap(compare);
  }
  empty() {
    return this.heap.empty();
  }
  push(item) {
    this.heap.insert(item);
  }
  pop() {
    if(!this.empty()) return this.heap.delete();
    else return null;
  }
}

let n = parseInt(input());
let pq = new PriorityQueue();
let result = '';
for(let i = 0; i < n; i++){
  let x = parseInt(input());
  if(x){
    pq.push(x);
  }
  else{
    if(pq.empty()) result += '0\n';
    else result += `${pq.pop()}\n`;
  }
}
console.log(result);

오랜만에 다시 우선순위 큐를 공부하기 위해 최소 힙 문제를 풀어봤었는데 전부 다 까먹었다. 처음부터 다시 공부해야했고 이참에 잊지 않게 정리하려고 한다.

javascript 에는 우선순위 큐 라이브러리가 없어 직접 만들어 사용해야 한다. 이왕 만드는거 최소 힙 과 최대 힙 그리고 객체간의 우선순위를 비교할 수 있게끔 비교함수를 커스텀할 수 있도록 heap 클래스를 작성했다.

• 힙은 1차원 배열로 구현되지만 이해를 위해 이진 트리 모양으로 그렸다.
• down, up heap 하는데 그려놓고 보니 전부 다 노드를 올리는 작업 뿐이다.

문제를 풀면서 고생했던 점은, 짧은 시간제한 때문에 받은 시간초과 였는데, 원인은 c++ 의 endl 처럼 느린 console.log 때문이였다.