[JavaScript] 백준 1927 : 최소 힙

class : 3
level : silver 2
문제 링크 : 최소 힙

1927번: 최소 힙

My Solution (1) - 메모리 초과

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n').map(Number);
const N = input.shift();
let arr = [],answer='';
input.forEach(value=>{
    if(value===0){
        if(arr.length>0){
            const min = Math.min(...arr);
            const index = arr.indexOf(min);
            arr = arr.slice(0,index).concat(arr.slice(index+1));
            answer+=`${min}\n`;
        }
        else{
            answer+='0\n';
        }
    }
    else
        arr.push(value);
})
console.log(answer.trim());

풀이방법 (1)
input을 줄바꿈 기준으로 분할하여 Array형태로 만들고 각각의 값을 숫자로 변환시켰다.
input을 forEach 메서드를 이용하여 value가 0이면 arr를 확인하고 arr의 크기가 0보다 크면 제일 작은 값을 answer에 추가하고 아니면 0을 추가한다.
이 때, arr에는 최솟값의 index를 찾아 arr에서 index를 제외하고 나머지를 연결시켰다.
value가 자연수일 경우에는 arr에 push하였다.
하지만 메모리 초과가 발생하였다.

My Solution (2) - 메모리 초과

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n').map(Number);
const N = input.shift();
let arr = [],answer='';
input.forEach(value=>{
    if(value===0){
        if(arr.length>0){
            arr.sort((a,b)=>a-b);
            answer+=`${arr.shift()}\n`;
        }
        else{
            answer+='0\n';
        }
    }
    else
        arr.push(value);
})
console.log(answer.trim());

풀이방법 (2)
첫 풀이에서 slice로 인하여 heap 메모리 부분이 overflow가 발생했다고 생각이 들어 arr에서 최솟값을 추출하는 경우에만 arr를 sort라는 메서드를 이용하여 오름차순으로 정렬 후 shift를 이용하여 가장 작은 값을 추출하려고 했다.
하지만 이 또한 메모리 초과가 발생했다.

My Solution - 최종

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n').map(Number);
const N = input.shift();
let minheap = [],answer='';
function insert(heap, num){
    heap.push(num);
    let ind = heap.length;
    while(ind>1){
        if(heap[Math.floor(ind/2)-1]>heap[ind-1]){
                const temp = heap[ind-1];
                heap[ind-1] = heap[Math.floor(ind/2)-1];
                heap[Math.floor(ind/2)-1] = temp;
                ind = Math.floor(ind/2);
        }
        else{
            break;
        }
    }
    return heap;
}
function del(heap){
    heap[0] = heap[heap.length-1];
    heap.pop();
    const len = heap.length;
    let ind = 1;
    while(ind*2<=len){
        if(heap[ind-1]>heap[ind*2-1] && (heap[2*ind]===undefined ||heap[ind*2-1] < heap[ind*2])){
            const temp = heap[ind*2-1];
            heap[ind*2-1] = heap[ind-1];
            heap[ind-1] = temp;
            ind = ind*2
        }
        else if(heap[ind-1]>heap[ind*2]){
            const temp = heap[ind*2];
            heap[ind*2] = heap[ind-1];
            heap[ind-1] = temp;
            ind = ind*2+1
        }
        else
            break;
    }
    return heap
}
input.forEach(value=>{
    if(value===0){
        if(minheap.length>0){
            answer+=`${minheap[0]}\n`;
            minheap = del(minheap)
        }
        else{
            answer+='0\n';
        }
    }
    else
        minheap = insert(minheap,value);
})
console.log(answer.trim());

풀이방법 - 최종
처음부터 Min Heap을 구현하였다.
따로 자료구조를 만들어 구현하지 않고 Array를 이용하여 구현하였다.(이유는 다른 자료구조를 만들어 사용하면 또 메모리 초과가 날 것이라고 생각하였기 때문이다.)
구현에서는 root를 0번 index에 넣었고 계산을 할 때는 1번으로 계산을 하였다.
delete가 예약어이기에 Min Heap의 원소 삭제 부분을 del이라 명명하였다.
heap에서 left node와 right node를 구분하여 넣어 주었지만 right node가 없는 경우를 생각을 안 해주고 아래와 같이 작성하였었다.

if(heap[ind-1]>heap[ind*2-1] && heap[ind*2-1] < heap[ind*2])

right node가 undefined이었을 경우를 생각을 못했기 때문이다. 따라서 다음과 같이 바꿔 작성하였다.
아래 부분은 위 코드의 28번째 줄의 if문이다.

if(heap[ind-1]>heap[ind*2-1] && (heap[2*ind]===undefined ||heap[ind*2-1] < heap[ind*2]))

느낀점
Heap이라는 자료구조를 복습하는 좋은 경험이라고 생각이 들었다.
아마 메모리 초과가 나는 부분은 가비지 컬렉션이 작동하기 전에 메모리가 128MB를 살짝 넘기지 않았을까라는 생각이 들었다.
함수형 프로그래밍을 위하여 내장 메서드를 잘 쓰려고 하였으나 내장 메서드가 메모리 초과를 발생시키는 원인이 될 수도 있구나라는 생각을 하였다.