[JavaScript] 야근 지수

level : 3
문제 링크 : 야근 지수

프로그래머스

My Solution

function solution(n, works) {
    let answer = 0;
    let maxheap = [];
    for(let i of works)
        insert(maxheap,i);
    while(n>0){
        const max = maxheap[0];
        remove(maxheap);
        insert(maxheap,max > 0 ? max - 1 : 0);
        n--;
    }
    answer += maxheap.reduce((pre,cur)=>pre+cur**2,0);
    return 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;
    }
}
function remove(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;
    }
}

풀이방법
처음에는 Math.max를 이용하여 매번 최댓값을 찾은 후 indexOf라는 메서드를 사용하여 최댓값을 1씩 감소시키는 방향으로 진행하였다.
하지만 효율성에서 시간초과가 발생하였다.
매번 sort하는 방식 또한 시간 초과가 발생하였다.

그리하여 Max Heap을 이용하였다.

maxheap이라는 Array에 Max Heap을 이용하여 0번째 index에 가장 큰 값을 가지는 배열을 만들었다.
n을 1씩 감소시키며 n이 0보다 클 때 동안 maxheap의 0번째 index에 있는 최댓값을 삭제 후 1씩 감소시켜 다시 maxheap에 삽입하였다. 이 때, 최댓값이 1보다 작을 경우 0을 삽입하였다.

이후 reduce라는 메서드를 이용하여 maxheap에 있는 원소들의 제곱의 합을 구하였다.

느낀점
Heap이라는 자료구조의 삽입 시간복잡도는 log(N)이며 삭제 시간복잡도 또한 log(N)이다. JavaScript의 기본 sort 메서드는 Tim Sort라고한다. Tim Sort는 기본적으로 시간복잡도가 N*log(N)이므로 매우 느리다는 것을 알 수 있다. 모든 것을 sort하는 방식보다는 원하는 것을 빠르게 찾을 수 있게 하는 것이 관건이었다.

Reference
https://woong-jae.com/javascript/220412-sort-implementation