프로그래머스 [Lv. 3] 야근 지수 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

정답 코드

function solution(n, works) {
    class heapq {
        constructor() {
            this.heap = [];
        };
        size() {
            return this.heap.length;
        };
        swap(left, right) {
            [this.heap[left], this.heap[right]] = [this.heap[right], this.heap[left]];
        };
        heappush(value) {
            this.heap.push(value);
            this.bubbleUp();
        };
        bubbleUp() {
            let son = this.heap.length - 1;
            let parent = Math.floor((son - 1) / 2);
            while (parent >= 0 && this.heap[son] > this.heap[parent]) {
                this.swap(son, parent);
                son = parent;
                parent = Math.floor((son - 1) / 2);
            };
        };
        heappop() {
            if (this.heap.length == 1) {
                return this.heap.pop();
            };
            const value = this.heap[0];
            this.heap[0] = this.heap.pop();
            this.bubbleDown();
            return value;
        };
        bubbleDown() {
            let root = 0;
            let left = 2 * root + 1;
            let right = 2 * root + 2;
            while (
                (left < this.heap.length && this.heap[left] > this.heap[root]) ||
                (right < this.heap.length && this.heap[right] > this.heap[root])
            ) {
                let tmp = left;
                if (right < this.heap.length && this.heap[right] > this.heap[tmp]) {
                    tmp = right;
                };
                this.swap(root, tmp);
                root = tmp;
                left = 2 * root + 1;
                right = 2 * root + 2;
            };
        };
    };

    const maxHeap = new heapq();
    
    works.forEach((e) => {
        maxHeap.heappush(e);
    })
    let tmp = n;
    while (tmp) {
        const maxV = maxHeap.heappop();
        if (maxV == 0) {
            break
        }
        maxHeap.heappush(maxV-1);
        tmp -= 1;
    }
    const answer = maxHeap.heap.reduce((res, e) => {
        return res += e ** 2;
    }, 0);
    
    return answer;
}

풀이 방법

1. 힙을 구현한다.
2. 힙에 값을 넣고 힙정렬을 시킨다.
3. heappop을 하면 가장 큰 값이 나오는데 -1을 해주고 tmp도 -1을 한다.
   1. 이 과정은 n이 0 즉, tmp가 0이 될 때까지 반복한다.
      1. heappop한 값이 0인 경우 종료 시켜도 좋을 것 같아서 수정했다.
4. reduce함수를 이용해 제곱한 값을 더해서 반환한다.

느낀점

• heap을 직접적으로 코테에서 적용할 수 있는 실력이 될 때까지 공부해야겠다.
• 이론은 알지만 기억력이 딸리는 것 같다.