[Javascript] 우선순위 큐 활용하여 문제 풀기 (1927 최소힙)

www.acmicpc.net/problem/1927

1927번: 최소 힙

 

우선순위 큐를 사용하는 간단한 문제인데,

python에서는 heap 라이브러리가 있어서 쉽게 풀 수 있었으나,

javascript에는 우선순위 큐를 직접 구현하여 해결해야한다는 것 때문에 조금 낮설었다.

앞으로 코딩테스트를 하면, 자바스크립트에서 제공하지 않는 라이브러리로 문제를 해결해야할 일이 많아질 텐데

템플릿을 복사해가며 문제를 해결해야할 것 같다는 생각을 했다.

 

아래는 MinHeap소스코드를 활용한 문제풀이이다.

 

'use strict'

function MinHeap() {
    this.heap = [0];

    this.insert = (v) => {
        this.heap.push(v);
        let p = this.heap.length - 1;
        while (p > 1 && this.heap[Math.floor(p / 2)] > this.heap[p]) {
            let tmp = this.heap[Math.floor(p / 2)];
            this.heap[Math.floor(p / 2)] = this.heap[p];
            this.heap[p] = tmp;
            p = Math.floor(p / 2);
        }
    };
    this.getLength = () => {
        return this.heap.length;
    }
    this.delete = () => {
        if (this.heap.length - 1 < 1) {
            return 0;
        }
        let deletedItem = this.heap[1];

        this.heap[1] = this.heap[this.heap.length - 1];
        this.heap.pop();

        let p = 1;
        while (p * 2 < this.heap.length) {
            let min = this.heap[p * 2];
            let minP = p * 2;
            if (p * 2 + 1 < this.heap.length && min > this.heap[p * 2 + 1]) {
                min = this.heap[p * 2 + 1];
                minP = p * 2 + 1;
            }
            if (this.heap[p] < min) {
                break;
            }

            let tmp = this.heap[p];
            this.heap[p] = this.heap[minP];
            this.heap[minP] = tmp;
            p = minP;
        }
        return deletedItem;
    };
}


const readline = require("readline");
const {
    parse
} = require("path");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const solution = (input) => {
    const q = new MinHeap();
    let answer = "";
    input.forEach(element => {
        element = parseInt(element);
        if (element > 0) {
            q.insert(element);
        } else {
            if (q.getLength() === 0) {
                answer += "0\n";
            } else {
                answer += `${q.delete()}\n`;
            }
        }
    });
    console.log(answer);
};

const input = [];
rl.on("line", function (line) {
    input.push(line);
}).on("close", function () {
    solution(input.slice(1));
    process.exit();
});