baekjoon. 최대 힙

문제

링크

풀이

힙을 구현해서 풀면되는 문제라서 따로 설명할 부분이 없다..

코드

    function solution(input){
        class Heap {
            constructor(arr = []) {
                this.arr = arr;
            }
            insert(elem){
                if(!this.arr.length){
                    this.arr.push(elem);
                } else {
                    this.arr.push(elem);
                    let parentIdx = Math.floor((this.arr.length-2)/2);
                    let child = this.arr.length-1;
                    while (this.arr[parentIdx]<this.arr[child]){
                        const temp = this.arr[parentIdx];
                        this.arr[parentIdx] = this.arr[child];
                        this.arr[child] = temp;
                        child = parentIdx;
                        parentIdx = Math.floor((child-1)/2);
                        if(parentIdx<0) parentIdx = 0;
                    }
                }
                return elem;
            }
            get(){
                return this.arr;
            }
            pop(){
                if(!this.arr.length) return 0;
                const last = this.arr.length;
                const temp = this.arr[0];
                this.arr[0] = this.arr[this.arr.length-1];
                this.arr[this.arr.length-1] = temp;
                const value = this.arr.pop();
                let parent =0;
                while (parent<last){
                    const left = parent*2+1;
                    const right = parent*2+2;

                    if(this.arr[right]> this.arr[parent] || this.arr[left]> this.arr[parent]) {
                        if (!this.arr[left]) break;
                        if(!this.arr[right]){
                            const temp = this.arr[parent];
                            this.arr[parent] = this.arr[left]
                            this.arr[left] = temp;
                            parent = left;
                        } else
                        if (this.arr[left] < this.arr[right]) {
                            const temp = this.arr[parent];
                            this.arr[parent] = this.arr[right]
                            this.arr[right] = temp;
                            parent = right;
                        } else {
                            const temp = this.arr[parent];
                            this.arr[parent] = this.arr[left]
                            this.arr[left] = temp;
                            parent = left;
                        }
                    } else break;
                }
                return value;
            }
        }

        const arr = input.split('\n').slice(1).map(v=>1*v);
        const heap = new Heap();

        let answer = '';

        for(let i=0; i<arr.length;i++){
            const temp = arr[i];
            if(temp===0) answer += heap.pop() +'\n';
            else heap.insert(temp);
        }
        console.log(answer);
    }