백준[node.js] > 1927번 최소 힙

문제링크

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

 

문제풀이, 후기

이 문제는 힙 자료구조를 이용해서 최솟 값을 구하는 연산을 최적화 하라는 문제라고 이해하면 된다. 

자바스크립트에서 힙 자료구조를 구현하기 위해서는 Class를 이용해서 직접 구현해야 하므로 직접 구현하여 풀었다.

참고로 초반엔 시간초과가 났는데 알고보니 console.log때문이었다. 매번 console.log를 하지 않고 답을 구한 뒤 한번의 console.log로 답을 출력하니 시간초과가 일어나지 않았다. 생각보다 console.log가 시간을 먹는다는 걸 알 수 있었다.

heap 구현은 능숙하였기 때문에 쉽게 풀 수 있었고 한번더 heap자료구조와 시간복잡도를 최적화 해주는 트리구조에 대해 생각해보는 계기가 되었다. 

 

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

// test case
// let data = "9\n0\n12345678\n1\n2\n0\n0\n0\n0\n32";
// let input = data
//     .toString()
//     .trim()
//     .split("\n")
//     .map((n) => Number(n));

let fs = require("fs");
let input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((n) => Number(n));

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

    insert(n) {
        let heap = this.heap;
        heap.push(n);
        if (heap.length >= 2) {
            let childIdx = heap.length - 1;
            let parentIdx = Math.floor((childIdx - 1) / 2);

            while (heap[parentIdx] > heap[childIdx]) {
                let [parent, child] = [heap[parentIdx], heap[childIdx]];

                heap[parentIdx] = child;
                heap[childIdx] = parent;

                childIdx = parentIdx;
                if (childIdx === 0) {
                    break;
                }
                parentIdx = Math.floor((childIdx - 1) / 2);
            }
        }
    }

    getMin() {
        let heap = this.heap;
        if (heap.length === 0) {
            return 0;
        }
        let min = heap[0];

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

        if (heap.length > 1) {
            let parentIdx = 0;

            let childIdx = undefined;

            if (heap[parentIdx * 2 + 2] && heap[parentIdx * 2 + 1] > heap[parentIdx * 2 + 2]) {
                childIdx = parentIdx * 2 + 2;
            } else if (heap[parentIdx * 2 + 1]) {
                childIdx = parentIdx * 2 + 1;
            }

            while (heap[parentIdx] > heap[childIdx]) {
                let [parent, child] = [heap[parentIdx], heap[childIdx]];

                heap[parentIdx] = child;
                heap[childIdx] = parent;

                parentIdx = childIdx;

                if (heap[parentIdx * 2 + 2] && heap[parentIdx * 2 + 1] > heap[parentIdx * 2 + 2]) {
                    childIdx = parentIdx * 2 + 2;
                } else if (heap[parentIdx * 2 + 1]) {
                    childIdx = parentIdx * 2 + 1;
                } else {
                    break;
                }
            }
        }

        return min;
    }
}

let minHeap = new MinHeap();

let answer = [];
for (let i = 1; i < input.length; ++i) {
    let number = input[i];

    if (number === 0) {
        answer.push(minHeap.getMin());
    } else {
        minHeap.insert(number);
    }
}

console.log(answer.join("\n"));