백준[node.js] > 11279번 최대 힙

문제링크

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

 

문제풀이

자바스크립트로 풀게 된다면 힙(heap) 구조를 직접 class로 구현해서 풀어야 한다.

힙 구조를 이용하면 계산횟수를 현저히 줄일 수 있다. 만약 힙구조에 대해 모른다면 이를 학습하고 이 문제를 풀기를 권한다.

힙구조에 대해 이해하고 있기 때문에 문제없이 해당 문제를 풀 수 있었다.

 

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

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

    push(num) {
        let heap = this.heap;

        heap.push(num);

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

            while (childIdx !== 0 && heap[parentIdx] < heap[childIdx]) {
                let [child, parent] = [heap[childIdx], heap[parentIdx]];

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

                childIdx = parentIdx;
                parentIdx = Math.floor((childIdx - 1) / 2);
            }
        }
    }

    popMax() {
        let heap = this.heap;

        if (heap.length === 0) {
            return 0;
        }

        if (heap.length === 1) {
            return heap.pop();
        }

        let max = heap[0];

        // 마지막 값 위로 올림
        heap[0] = heap.pop();

        let parentIdx = 0;
        // 왼쪽, 오른쪽 자식 idx
        let leftChildIdx = parentIdx * 2 + 1;
        let rightChildIdx = parentIdx * 2 + 2;

        while (
            (heap[leftChildIdx] && heap[leftChildIdx] > heap[parentIdx]) ||
            (heap[rightChildIdx] && heap[rightChildIdx] > heap[parentIdx])
        ) {
            // 부모값값
            let parent = heap[parentIdx];

            // 왼쪽 자식을 최댓값으로 간주
            let child = heap[leftChildIdx];
            let childIdx = leftChildIdx;

            if (heap[rightChildIdx] && heap[rightChildIdx] > heap[leftChildIdx]) {
                // 오른쪽 자식이 최댓값으로 판명됨
                child = heap[rightChildIdx];
                childIdx = rightChildIdx;
            }

            // 자식과 부모 값 체인지
            heap[parentIdx] = child;
            heap[childIdx] = parent;

            // 다시 부모, 좌측자식, 우측자식 세팅
            parentIdx = childIdx;
            leftChildIdx = parentIdx * 2 + 1;
            rightChildIdx = parentIdx * 2 + 2;
        }

        return max;
    }
}

const maxHeap = new MaxHeap();

const N = input.shift();

let str = "";
for (let i = 0; i < N; ++i) {
    let n = input[i];

    if (n === 0) {
        str += `${maxHeap.popMax()}\n`;
    } else {
        maxHeap.push(n);
    }
}
console.log(str.trim());