[프로그래머스/Javascript/Heap] 디스크 컨트롤러

1. 서론

 위 문제는 Heap으로 분류되어 있으나, javascript 에서는 Heap에 대한 라이브러리가 존재하지 않기때문에 직접 구현해야한다. heap에 대한 코드는 이전에 작성한 jun0127.tistory.com/11 에 있는 코드를 그대로 사용하였다.

 

2. 문제 설명(출처: programmers.co.kr/learn/courses/30/lessons/42627)

3. 문제 풀이

 1) 하드 디크스가 작업을 수행하고 있지 않을 때는 먼저 요청이 들어온 작업부터 처리합니다. 라고 하였으니 jobs를 시간 순서대로 먼저 정렬해준다.

 2) 작업을 수행하고 있을 때, 들어온 순서대로 작업하면 최소시간을 보장하지 못한다. 따라서 우선순위 큐에 시간 순서대로 작업을 enqueue 해야한다.

 3) 최초의 작업이 끝나면, 해당 시간에 우선순위 큐에 있는 작업들 중 처리시간이 가장 작은 작업을 수행한다.

 4) 이 과정을 jobs가 모두 끝날 때까지 반복한다.

 5) 마지막으로 총 걸린 시간을 작업의 갯수만큼 나눠 평균 시간을 계산하고 반환한다.

 

4. 결과 코드

function solution(jobs) {
  var answer = 0;
  var q = new PriorityQueue()
  var len = jobs.length

  jobs.sort((a, b) =>a[0] - b[0]);
  var time = 0
  while(jobs.length || !q.isEmpty()){
    let job_length = jobs.length
    for(let i = 0; i < job_length; i++){
      if(jobs[0][0] <= time){
        q.enqueue(jobs[0][1], jobs[0][0])
        jobs.shift()
      }else{
        break
      }
    }
    
    if(!q.isEmpty()){
      let node = q.dequeue()
      time += node.key
      answer += time - node.value
    }else{
      time++
    }
  }

  return Math.floor(answer / len)
}