[JS] 야근 지수

 

힙을 활용해서 해결하였다.

 

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

프로그래머스

 

 

야근지수를 가장 낮게 받는 방법은 생각보다 간단하다. 현재 남은 피로도 중에서 가장 큰값부터 피로도를 깎으면 된다.

문제 조건또한 1000000정도라서 시간도 충분할꺼라 생각했다.

 

이런 문제는 이분탐색을 활용해도 되고 힙을 활용해도 되는데 힙을 활용했다.

 

우선순위 큐를 활용하여 해결하였다.

 

 

 

 

class MaxHeap {
    constructor(){
        this.ary = [0]
    }
    swap(a,b) {
        [this.ary[a],this.ary[b]] = [this.ary[b],this.ary[a]]
    }
    push(value){
        this.ary.push(value)
        let idx = this.ary.length - 1
        while(idx>1){
            const parent = ~~(idx/2)
            if(this.ary[parent]>=this.ary[idx]) break
            this.swap(parent,idx)
            idx = parent
        }
    }
    pop(){
        if(this.ary.length===1) return undefined
        if(this.ary.length===2) return this.ary.pop()
        const ret = this.ary[1]
        this.ary[1] = this.ary.pop()
        let idx = 1
        while(idx < this.ary.length){
            const [left,right] = [idx*2,idx*2+1]
            let maxIdx = left
            if(left >= this.ary.length) break
            if(right < this.ary.length && this.ary[right] > this.ary[left])
                maxIdx = right
            if(this.ary[maxIdx] <= this.ary[idx]) break
            this.swap(maxIdx,idx)
            idx = maxIdx
        }
        return ret
    }
}

function solution(n, works) {
	//힙 생성
    const heap = new MaxHeap()
    for (const work of works){
        heap.push(work)
    }
    
    //가장 큰값의 수를 줄임
    for (let i = 0 ; i < n ; i++){
        const num = heap.pop()
        if (num>1) heap.push(num-1)
    }
    
    //힙에 남은 값들 다 더하기
    return heap.ary.reduce((a,c) => a+c**2 , 0)
    
 
}