[프로그래머스 Level 3] 야근 지수 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(n, works) {
    class PriorityQueue {
        constructor() {
            this.heap = [];
        }

        push(value) {
            const { heap } = this;
            heap.push(value);

            let index = heap.length - 1;
            let parent = Math.floor((index - 1) / 2);

            while (index > 0 && heap[index] > heap[parent]) {
                [heap[index], heap[parent]] = [heap[parent], heap[index]];
                index = parent;
                parent = Math.floor((index - 1) / 2);
            }
        }

        pop() {
            const { heap } = this;

            if (!heap.length) {
                return heap.pop();
            }

            const output = heap[0];
            heap[0] = heap.pop();
            let index = 0;

            while (index * 2 + 1 < heap.length) {
                let left = index * 2 + 1;
                let right = index * 2 + 2;
                let next = index;

                if (heap[left] > heap[next]) {
                    next = left;
                }

                if (right < heap.length && heap[right] > heap[next]) {
                    next = right;
                }

                if (index === next) {
                    break;
                }

                [heap[index], heap[next]] = [heap[next], heap[index]];
                index = next;
            }

            return output;
        }
    }

    const workQueue = new PriorityQueue();
    works.forEach(work => workQueue.push(work));

    for (let i = 0; i < n; i++) {
        const work = workQueue.pop();
        if (!work) {
            return 0;
        }
        workQueue.push(work - 1);
    }

    return workQueue.heap.reduce((acc, v) => acc + v ** 2, 0);
}

가장 큰 작업량을 1씩 줄여나가는 방식으로 일해야 야근 피로도를 최소로 만들 수 있다.

 

가장 큰 작업량의 일을 1만큼 처리하고, 방금 처리한 일을 포함한 모든 일 중에서 다시 또 가장 큰 작업량의 일을 1만큼 처리하기를 계속해서 n번 반복하면 된다. 이 때, 일을 1만큼 처리한 후에 다시 가장 큰 작업량의 일을 찾으려면 매번 일들을 작업량의 크기로 정렬해야 하는데, 우선순위 큐를 활용하면 이를 O(log N)의 시간복잡도로 가장 큰 작업량의 일을 찾을 수 있다.

 

n번 반복 하는 도중에 우선순위 큐에서 pop된 일의 작업량이 0이라면 모든 작업을 마쳤다는 뜻이므로 즉시 0을 반환한다. 반복문이 종료되면 우선순위 큐의 heap에 있는 모든 값들을 제곱하여 그 합을 반환하였다.