baekjoon. 절댓값 힙

문제

링크

풀이

바로 직전에 풀었던 문제인 최대 힙과 거의 유사하게 풀리는 문제

정렬시에 절대값으로 비교해야하는 조건이 있기 때문에 그 부분만 잘 구현해주면된다

이전 문제에서 구현했던 힙이 많이 지저분해서 나름 깔끔하게 다시 구현하려고 노력했지만.. 나는 만족한다

코드

    function solution(input){
        class Heap{
            constructor(arr = []) {
                this.arr = arr;
            }
            insert(elem){
                this.arr.push(elem);
                let child = this.arr.length-1;
                let parent = Math.floor((this.arr.length-2)/2);

                while (this.getAbsolut(parent)>=this.getAbsolut(child)){
                    if(this.getAbsolut(parent)===this.getAbsolut(child) && this.getValue(parent) < this.getValue(child)){}
                    else this.swap(parent,child);
                    child = parent;
                    parent = Math.floor((child-1)/2);
                }
            }
            swap(parent,child){
                const temp = this.arr[child];
                this.arr[child] = this.arr[parent];
                this.arr[parent] = temp;
            }
            pop(){
                if(!this.arr.length) return 0;
                const lastIdx = this.arr.length;
                this.swap(0, lastIdx-1);
                const temp = this.arr.pop();
                let parent = 0;
                while (parent<lastIdx){
                    const left = parent*2+1;
                    const right = parent*2+2;

                    if(this.getAbsolut(left) <= this.getAbsolut(parent) || this.getAbsolut(right) <= this.getAbsolut(parent)) {
                        if (!this.arr[left]) break;
                        if (!this.arr[right]) {
                            if(this.getAbsolut(left) <= this.getAbsolut(parent)){
                                if(this.getValue(left) < this.getValue(parent)){
                                    this.swap(parent, left);
                                    parent = left;
                                }
                            }
                            break;
                        }
                        if (this.getAbsolut(left) < this.getAbsolut(right)) {
                            this.swap(parent, left);
                            parent = left;
                            continue;
                        }
                        if (this.getAbsolut(left) > this.getAbsolut(right)) {
                            this.swap(parent, right);
                            parent = right;
                            continue;
                        }
                        if(this.getValue(left)< this.getValue(right)){
                            this.swap(parent,left);
                            parent = left;
                            continue;
                        }
                        this.swap(parent,right);
                        parent = right;
                    } else break;
                }

                return temp;
            }
            getValue(index){
                return this.arr[index];
            }
            getAbsolut(index){
                return Math.abs(this.arr[index]) || false;
            }
        }

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

        const heap = new Heap();
        let answer = '';
        for(let v of arr){
            if(!v) answer += heap.pop() + '\n';
            else heap.insert(v);
        }
        console.log(answer);
    }