[BaekJoon] 1655번 가운데를 말해요 문제 - (nodejs)

문제 번호 :  1655번

문제 바로가기 ☞ https://www.acmicpc.net/problem/1655

---

 

<<< 문제 내용 >>>

---

 

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

let [n, ...arr] = input.split('\n').map((el) => Number(el));

class Heap{
    constructor(){
        this.node = [];
    }

    insert(data, status){
        this.node.push(data);
        let child = this.node.length-1;
        
        if(status === 'max'){
            while(child !== 0){
                let parent = Math.floor((child-1)/2);
                
                if(this.node[parent] < this.node[child]){
                    this.swap(parent,child);
                    child=parent;
                } else {
                    break;
                }
            }
        }else{
            while(child !== 0){
                let parent = Math.floor((child-1)/2);
                
                if(this.node[parent] > this.node[child]){
                    this.swap(parent,child);
                    child=parent;
                } else {
                    break;
                }
            }
        }
    }

    delete(status){
        if(this.node.length===1) return this.node.pop();

        let topNode = this.node[0];

        this.node[0] = this.node.pop();

        let parent = 0;

        if(status === 'max'){
            while (true) {
                const leftchild = parent * 2 + 1;
                const rightchild = parent * 2 + 2;
                let currentNode = parent;

                // Left
                if (this.node[leftchild] !== undefined && this.node[leftchild] > this.node[currentNode]) currentNode = leftchild;

                if (this.node[rightchild] !== undefined && this.node[rightchild] > this.node[currentNode]) currentNode = rightchild;

                if (currentNode !== parent) {
                    this.swap(parent, currentNode);
                    parent = currentNode;
                } else break;
            }
        }else{
            while (true) {
                const leftchild = parent * 2 + 1;
                const rightchild = parent * 2 + 2;
                let currentNode = parent;

                // Left
                if (this.node[leftchild] !== undefined && this.node[leftchild] < this.node[currentNode]) currentNode = leftchild;

                if (this.node[rightchild] !== undefined && this.node[rightchild] < this.node[currentNode]) currentNode = rightchild;

                if (currentNode !== parent) {
                    this.swap(parent, currentNode);
                    parent = currentNode;
                } else break;
            }
        }

        return topNode;
    }

    swap(y, x){
        [this.node[y], this.node[x]] = [this.node[x], this.node[y]];
    }
}

const maxHeap = new Heap();
const minHeap = new Heap();
const answer = [];

for(let i of arr){
    if(maxHeap.node.length === minHeap.node.length){
        maxHeap.insert(i, 'max');
    }else{
        minHeap.insert(i, 'min');
    }

    if(minHeap.node.length === 0) answer.push(maxHeap.node[0]);
    else {
        if(maxHeap.node[0] > minHeap.node[0]){
            const temp = minHeap.delete('min');
            const temp2 = maxHeap.delete('max');
            minHeap.insert(temp2, 'min');
            maxHeap.insert(temp, 'max');
        }
        answer.push(maxHeap.node[0]);
    }
}

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

 

* 이 문제는 시간초과가 0.1초로 매우 효율좋은 알고리즘을 사용해야 합니다.

그 중 중간값을 실시간으로 찾는 가장 좋은 방법은 priority queue(우선순위 큐)를 이용하는 문제입니다.

 

 

먼저 이 문제는 중앙 값을 실시간으로 찾아야합니다.

 

[최대 힙] ---- 중앙 값 ---- [최소 힙] 을 기준으로 문제가 풀이됩니다.

 

기본적으로는 최대 힙에 값을 넣고, 최대 힙의 length와 최소 힙의 length가 다르면 최소 힙에 값을 넣어줍니다.

* 따라서 최대 힙 - 최소 힙 - 최대 힙 - 최소 힙 순서로 번갈아가면서 값이 들어가게 됩니다.

 

그 이후, 최대 힙의 최상위 노드와 최소 힙의 최상위 노드의 값을 비교해 만약 최대 힙이 최소 힙 보다 크다면

둘의 최상위 노드를 뽑아낸 후 서로에게 반대로 넣어주면서 최대 힙의 최상위 노드를 출력하면 중앙 값을 찾을 수 있습니다.

-- 이때, 최상위 노드끼리의 값만 바꿔주는 것이 아닙니다!!! 저도 여기서 시간을 많이 뺏겼습니다..!! ---

 

 

 

만약, 3 1 4 2 3 으로 각각의 값을 push 해본다면,

 

[최대 힙] ------------------------ 중앙 값 ------------------------ [최소 힙]
     3                          [최대힙의 최상위 노드] 

---------------------------------------------------------------------------------
     1                                                                                3

---------------------------------------------------------------------------------
     3                                                                                4          [최대 힙에 4를 넣었지만 최소 힙의
1                                                                                                 0번째가 더 커서 변경]

---------------------------------------------------------------------------------
     2                                                                                3
1                                                                                4

---------------------------------------------------------------------------------
     3                                                                                3
1        3                                                                       4

 

이렇게 됩니다.

 

안타깝게도 C++, Python 등과 같은 언어에서 제공하는 priority queue가 js에서는 따로 없기 때문에,

직접 구현해야 합니다.

 

한번 원리만 이해한다면 비슷한 유형의 문제에 적용하기는 굉장히 쉽습니다.

 

템플릿처럼 만들어 둔다면, 편하게 사용가능할 것 같습니다.

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.