Javascript 백준 2075 N번째 큰 수

로직

• 입력값의 숫자들을 우선순위 큐에 넣으면서 갱신하는 형태
• N번째 큰 수를 찾으면 되므로 큐의 크기를 N으로 유지하며 작은 값을을 쳐내는 구조

고민한 것

• 처음에는수의 배열이 자기보다 위에 있는 숫자보다는 크다는 점을 이용하려고 했습니다.
  • 맨 마지막 줄의 숫자들을 우선순위 큐에 넣고
  • 그 중 가장 큰 수를 빼면서 그 위에 있는 숫자를 넣는다
  • 이를 N번 반복한 결과값이 N번째 큰 수
• 그래서 2중 배열 형태로 숫자를 저장하려고 했습니다.
• 하지만 메모리 제한이 12mb로 최대 N 값인 1500*1500 크기로 array를 저장시 메모리 부족으로 실패하게 됩니다.
• 그렇기에 위 방법으로는 해결할 수가 없어서 입력값이 들어오는대로 처리하고 메모리를 없애야 문제가 해결이 됩니다.

readLine ?

• python으로 알고리즘 문제를 풀때는 sys.stdin.readline 을 이용
• Javascript(nodeJS)의 경우 파일을 읽어 input값을 한번에 받아들였으나, 이 문제는 메모리가 넉넉하지 않아 문제가 발생
• 그래서 알아본 것이 nodeJS의 readline
• 디버깅?
  • 어느때와 같이 vscode 디버깅을 하려고 f5로 시작하였으나, 잘 안됨
  • 터미널에 node 파일명입력으로 테스트 가능

자료구조

• python의 경우 heapq자료구조가 내장되어 있어 애용
• javascript(nodeJS)의 경우 우선순위 큐가 없기에 직접 구현해야 했음
  • nodeJS 알고리즘 문제 풀이의 문제
• 완전 이진트리 구조로 구성하고, 값을 변경하거나 추가하며 우선순위 큐 구현
  • 2년만에 구현해봐서 고생;

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

    push(value){
        let cur = this.heap.length;
        let parent;
        while (cur > 1){
            parent = Math.floor(cur/2);
            if (value < this.heap[parent]) {
                this.heap[cur] = this.heap[parent];
                cur = parent;
            } else break;
        }
        this.heap[cur] = value;
    }

    pop(){
        if (this.heap.length === 1) return null;
        if (this.heap.length === 2) return this.heap.pop();
        const popValue = this.heap[1];
        this.heap[1] = this.heap.pop();
        let cur = 1;
        let left = cur*2;
        let right = cur*2+1;
        while (this.heap[left]){
            let childIdx = left;
            if (this.heap[right] && this.heap[left] > this.heap[right]) childIdx = right;
            if (this.heap[cur] > this.heap[childIdx]){
                [this.heap[cur],this.heap[childIdx]] = [this.heap[childIdx],this.heap[cur]];
                cur = childIdx;
                left = cur * 2;
                right = cur * 2 + 1;
            } else break;
        }
        return popValue;
    }

    size(){
        return this.heap.length -1;
    }
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let N = -1;
let cnt;
const que = new MinHeap()
rl.on("line",(line)=>{
    if (N === -1){
        N = parseInt(line);
        cnt = N;
        idxCheck = new Array(N).fill(N-1);
        return;
    }
    const temp = line.split(' ').map(Number);
    temp.forEach((num,idx)=>{
        que.push(num);
        if (que.size() > N) que.pop();
    })
    cnt -= 1
    if (cnt === 0){
        rl.close();
    }
}).on('close',()=>{
    console.log(que.pop())
})