(프로그래머스 JS)야근 지수

https://programmers.co.kr/learn/courses/30/lessons/12927?language=javascript

코딩테스트 연습 - 야근 지수

 

최대힙(max heap)을 이용한 문제 풀이.

 

최대힙을 클래스로 구현하고, 이 힙에 works의 요소를 하나씩 push한다.

push하게 되면 알아서 최대힙으로 정렬이 된다.

 

이후 n만큼 반복하면서 힙을 순회한다.

pop()을 하게 되면 가장 큰 수가 앞에 나오게 되며,

해당 일이 0이 아닌 경우 -1을 하여 다시 힙에 넣어주게 된다.

(일의 양이 0인 경우 끝났기 때문에)

 

n만큼 반복했다면 이제 남아있는 일의 야근 지수를 구하면 된다.

heap을 빌 때까지 while문을 돌면서

남아있는 일의 양을 제곱하여 answer에 넣어주면 끝!

class PriorityQueue {
    constructor(){
        this.queue = [0];
        this.size = 0;
    }
    
    push(value) {
        this.queue.push(value);
        this.size++;
        
        this.moveUp(this.size);
    }
    
    moveUp(index){
        while(Math.floor(index / 2)){
            const parent = Math.floor(index / 2);
            
            if(this.queue[parent] < this.queue[index]){
                [this.queue[parent], this.queue[index]] = [this.queue[index], this.queue[parent]];
            }
            
            index = parent;
        }
    }
    
    pop() {
        const maxValue = this.queue[1];
        this.queue[1] = this.queue[this.size];
        
        this.queue.pop();
        this.size--;
        
        this.moveDown(1);
        
        return maxValue;
    }
    
    moveDown(index) {
        while(index * 2 <= this.size){
            const maxChildIndex = this.findMaxChildIndex(index);
            
            if(this.queue[index] < this.queue[maxChildIndex]){
                const tmp = this.queue[maxChildIndex];
                this.queue[maxChildIndex] = this.queue[index];
                this.queue[index] = tmp;
            }
            
            index = maxChildIndex;
        }
    }
    
    findMaxChildIndex(index) {
        const left = index * 2;
        const right = (index * 2) + 1;
        
        if(right > this.size){
            return left;
        } else{
            if(this.queue[right] > this.queue[left]){
                return right;
            } else{
                return left;
            }
        }
    }    
}

function solution(n, works) {
    let answer = 0;
    const heap = new PriorityQueue();
    
    for(let i = 0; i < works.length; i++){
        heap.push(works[i]);
    }
    
    for(let i = 0; i < n; i++){
        const work = heap.pop();

        if(work !== 0){
            heap.push(work - 1);
        }
    }
    
    while(heap.size){
        const work = heap.pop();
        
        answer += (work ** 2);
    }
    
    return answer;
}