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

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

프로그래머스

문제 설명

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다. Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해 주세요.

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1
n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간 동안 일을 한 결과는 [2, 2, 2]입니다. 이때 야근 지수는 22 + 22 + 22 = 12 입니다.

 

입출력 예 #2
n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간 동안 일을 한 결과는 [1,1,2]입니다. 야근지수는 12 + 12 + 22 = 6입니다.

 

입출력 예 #3

남은 작업량이 없으므로 피로도는 0입니다.

---

문제 풀이

이 문제를 다 읽고, 처음 생각난 아이디어는 아래와 같았습니다.

[ n번 동안 1 - 4번 과정을 반복 ]
 
1. 내림차순 정렬하기
2. 첫 번째 숫자를 얻기 위해 shift 사용하기
3. shift한 숫자에 1을 빼주기
4. 다시 배열에 push 하기

 

하지만, 자바스크립트에서의 sort는 O(nlogn)의 시간복잡도를 가지고 있고, 이를 n번 반복하면 O(n(logn)^2)이 됩니다.

무조건 시간 초과가 생길 것으로 예상했고, sort를 대신할 수 있는 방법을 고민하였습니다.

 

우선 위에서 생각한 방법은 무조건 배열에서 제일 큰 숫자가 맨 앞에 위치해 있으며, 맨 앞 숫자를 가져올 수 있어야 하고, 다시 숫자를 넣었을 때 재정렬이 되어야 했습니다.

다시 읽어보니 뭔가 생각나지 않으신가요? 😀

 

저는 '우선순위 큐'를 떠올렸습니다.

1. 우선순위 큐에 숫자를 다 넣는다.
    > enqueue(O(logn))가 n번 반복 => nlogn
2. 맨 첫 번째 숫자를 가져온다.
    > dequeue(O(logn)) => logn
3. 숫자에서 1을 빼고, 다시 우선순위 큐에 넣는다.
    > enqueue(O(logn)) => logn
4. 2번과 3번을 n번 반복한다.
    > O(2logn) * n => 2nlogn

즉, O(nlogn)의 시간복잡도를 가지면서,  sort를 사용했을 경우보다 훨씬 시간을 적게 사용하고 있음을 알 수 있습니다.

❗'우선순위 큐'에 대한 코드는 아래 사이트에서 소개하고 있는 코드를 외워서 사용하고 있어요❗
https://walkccc.me/CS/JavaScript/04/MaxPriorityQueue/

Max Priority Queue - Computer Science Notes

제출 코드

class Node {
    constructor(value) {
        this.value = value
    }
}

class PriorityQueue {
    constructor() {
        this.queue = [];
    }
    
    enqueue(value) {
        const newNode = new Node(value);
        
        this.queue.push(newNode);
        this.bubbleUp();
    }
    
    bubbleUp() {
        let index = this.queue.length - 1;
        let node = this.queue[index];
        
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            let parentNode = this.queue[parentIndex];
            
            if (node.value <= parentNode.value) break;
            
            this.queue[parentIndex] = node;
            this.queue[index] = parentNode;
            index = parentIndex;
        }
    }
    
    dequeue() {
        const dequeueNode = this.queue[0];
        const node = this.queue.pop();
        
        if (this.queue.length > 0) {
            this.queue[0] = node;
            this.bubbleDown();
        }
        
        return dequeueNode;
    }
    
    bubbleDown() {
        const len = this.queue.length;
        let index = 0;
        const node = this.queue[index];
        
        while (true) {
            let leftChildIndex = index * 2 + 1;
            let rightChildIndex = index * 2 + 2;
            let leftChild = null;
            let rightChild = null;
            let swapIndex = null;
            
            if (leftChildIndex < len) {
                leftChild = this.queue[leftChildIndex];
                
                if (leftChild.value > node.value) {
                    swapIndex = leftChildIndex;
                }
            }
            
            if (rightChildIndex < len) {
                rightChild = this.queue[rightChildIndex];
                
                if (
                    (swapIndex === null && rightChild.value > node.value) ||
                    (swapIndex !== null && rightChild.value > leftChild.value)
                ) {
                    swapIndex = rightChildIndex;
                }
            }
            
            if (swapIndex === null) break;
            
            this.queue[index] = this.queue[swapIndex];
            this.queue[swapIndex] = node;
            index = swapIndex;
        }
    }
}

function solution(n, works) {
    const queue = new PriorityQueue();
    
    for (let work of works) {
        queue.enqueue(work);
    }
    
    for (let i = 0; i < n; i++) {
        let value = queue.dequeue().value;
        value -= 1;
        
        if (value < 0) return 0;
        
        queue.enqueue(value);
    }
    
    let result = 0;
    
    for (let i = 0; i < works.length; i++) {
        const value = queue.dequeue().value;
                
        result += Math.pow(value, 2);
    }
    
    return result;
}