[JS] 디스크 컨트롤러

heap을 이용하여 해결하였다.

 

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

프로그래머스

 

 

제한 사항

 

사실 문제 제한사항이 널널한 편이라 sort함수를 써도 통과가 될 것 같긴 하다. ( 실제로도 다른 풀이를 보면 그런듯 )

 

문제에서 중요한 점은 , 일을 처리할 수 있는 최소한의 경우의 수를 찾는 문제가 아닌 실제 테스크 큐가 작동하는 것처럼 현재 디스크가 일을 안하고 있다면 작업을 바로 수행하는게 요점이다.

 

따라서 테스크 큐 역할을 하는 heap을 하나 만들어서 아래와 같은 흐름으로 해결하였다.

 

1. 현재 시간에서 받을 수 있는 요청들을 다 테스크 큐에 넣음

2. 최소힙을 써서 걸리는데 가장 시간이 적게드는 작업을 수행

3. 해당 작업시간만큼 time을 더해줌

4. 만약 테스크 큐가 비어있다면 시간을 1초 더해줌

 

 

왜 가장 시간이 적게드는 작업을 먼저 수행하는지에 대해 헷갈릴 수 있는데 간단하게 생각해보면 이해할 수 있다.

 

어차피 디스크가 일을 하는 기간동안 큐에있는 요청들은 동일하게 시간을 가져야한다 즉, 테스크 큐에 있는 요청의 수가 적을 수록 더해지는 대기시간이 줄어든다. 따라서 최대한 빨리 테스크 큐를 비우기 위해서 작업시간이 적은 작업부터 진행시키는 것이다.

 

 

 

 

 

class MinHeap {
    constructor (){
        this.ary = [0]
    }
    
    swap(a,b){
        [this.ary[a],this.ary[b]] = [this.ary[b],this.ary[a]]
    }
    
    push(val){
        let idx = this.ary.length
        this.ary.push(val)
        
        while (idx > 1){
            const parentIdx = ~~(idx/2)
            if(this.ary[parentIdx][1] > this.ary[idx][1]) {
                this.swap(idx,parentIdx)
                idx = parentIdx
            }
            else break
        }
    }
    
    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 = idx * 2
            const right = idx * 2 + 1
            if (left >= this.ary.length) break
            let minIdx = left
            if (right < this.ary.length && this.ary[right][1] < this.ary[left][1])
                minIdx = right
            if (this.ary[minIdx][1] < this.ary[idx][1]) {
                this.swap(minIdx,idx)
                idx = minIdx
            } else break
        }
        return ret
    }
}

function solution(jobs) {
    const len = jobs.length
    jobs.sort((a,b) => b[0]-a[0])
    
    const heap = new MinHeap()
    
    let ret = 0
    let time = 0
    while(jobs.length || heap.ary.length>1) {
        while(jobs.length && jobs[jobs.length-1][0] <= time)
            heap.push(jobs.pop())
        
        
        if(heap.ary.length>1){
            const curTask = heap.pop()
            
            ret += curTask[1] + time - curTask[0]
            time += curTask[1]
        } else {
            time += 1
        }
    }
    
    return ~~(ret / len)
    
}