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

문제 번호

프로그래머스

 

 

 

알고리즘 분류

• 우선 순위 큐

 

문제 풀이

 우선순위 큐를 활용하면 문제를 해결 할 수 있다.

문제에서 주어진 works를 살펴보면 works중 가장 큰 수가 가장 작아질 때가 정답이다. 따라서 MaxHeap을 사용해서 works에 남아있는 수 들 중에서 가장 큰 수를 1씩 줄여나가면 된다.

 

MaxHeap

class Node{
    constructor(value) {
        this.value = value;
    }
}
class MaxHeap{
    constructor(compare){
        this.heap = [];
        this.compare = compare;        
    }
    empty() {
        return !this.heap.length;
    }
    push(value) {
        const newNode = new Node(value);
        this.heap.push(newNode);
        if(this.heap.length >= 1) {
            let curIdx = this.heap.length-1;
            let curItem = this.heap[curIdx];
            while(curIdx > 0) {
                let parentIdx = Math.floor((curIdx-1)/2);
                let parentItem = this.heap[parentIdx];
                
                if(this.compare(parentItem.value, curItem.value)) break;
                
                this.heap[curIdx] = parentItem;
                curIdx = parentIdx;
            }
            this.heap[curIdx] = curItem;
        }        
    }
    pop(){
        const lastIdx = this.heap.length-1;
        this.heap[0] = this.heap[lastIdx];
        this.heap.pop();
        if(this.heap.length >= 1) {
            let curIdx = 0;
            let curItem = this.heap[curIdx];
            while(curIdx < this.heap.length) {
                let leftIdx = curIdx*2+1;
                let rightIdx = curIdx*2+2;
                
                if(leftIdx >= this.heap.length) break;
                
                let leftItem = this.heap[leftIdx];
                let rightItem = rightIdx < this.heap.length
                ? this.heap[rightIdx]
                : null;
                
                let nextIdx = rightItem !== null && this.compare(rightItem.value, leftItem.value)
                ? rightIdx
                : leftIdx;
                let nextItem = this.heap[nextIdx];
                
                if(this.compare(curItem.value, nextItem.value)) break;
                
                this.heap[curIdx] = nextItem;
                curIdx = nextIdx;
            }
            this.heap[curIdx] = curItem;
        }
    }
    peek(){
        return this.heap[0].value;
    }
}

 

전체 코드

function solution(n, works) {
    let answer = 0;
    const MH = new MaxHeap((a,b)=>a>b);
    for(const item of works) {
        MH.push(item)
    }
    while(!MH.empty() && n > 0) {
        let work = MH.peek();
        if(work - 1 < 0) work = 0;
        else work -= 1;
        MH.pop();
        MH.push(work);
        n -= 1;        
    }
    while(!MH.empty()) {        
        answer += MH.peek()**2;
        MH.pop();
    }
    return answer;
}

 

특이사항