[프로그래머스] Lv3. 디스크 컨트롤러 (자바스크립트)

최소힙과 SJF 알고리즘을 사용해서 풀어야 하는 문제 !

문제 핵심

1. 진행중인 작업이 없을때는 들어온 순서대로 작업을 시작한다.
2. 작업 진행중에 들어온 작업들은 대기열에 넣어둔다.
3. 앞의 작업이 끝나면 대기열의 작업들 중 소요시간이 가장 작은 작업 먼저 진행한다.
4. 남아있는 작업이 0개가 될때까지 반복한다.

코드 이해하기

일단 가장 먼저 들어온 작업을 진행시키기 위해 들어온 시간 순서대로 오름차순 정렬을 해줍니다. (같은 시간에 들어온 작업들도 소요시간이 작은 작업이 앞순으로 정렬됨)

jobs.sort((a,b) => a[0] - b[0]);

currTime 변수는 현재 시간을 나타내고, 작업이 초단위로 들어오기 때문에 1초씩 증가하도록 해줍니다.

currTime ++;

작업이 요청되는 시간이 현재 currTime시간과 같은 작업이 있다면 heap에 넣어 대기시킵니다. 처음으로 들어온 [0,3] 작업은 0초일때 작업 대기열에 들어가게 됩니다.

while( jobs.length > 0){
      if( jobs[0][0] === currTime ){
      minHeap.add(jobs.shift());
      }else break;
    }  

마찬가지로 첫 작업은 currTime과 completeTime이 0으로 일치해 대기열에 들어가자마자 호출되어 작업을 시작하게 됩니다. 이후 completeTime을 첫번째 작업이 끝날 때의 시간으로 바꾸고 해당 작업이 진행 중일 때는 다른 작업들을 호출할 수 없도록 해줍니다.

if(minHeap.size() > 0 && currTime >= completeTime){
      let task = minHeap.poll();
      completeTime = task[1] + currTime;
      totalTime += completeTime - task[0];
    }

totalTim은 작업을 요청한 시점부터 작업이 완료된 시간까지의 총 소요시간입니다. 즉, 작업이 완료된 시간에서 작업을 요청한 시간만큼을 뺴주면 총 소요시간을 얻을 수 있습니다.

전체 코드

function solution(jobs) {
class Heap{
        constructor() {
    this.heap = [];
  }
  
  swap(index1,index2){
    [this.heap[index1], this.heap[index2]] = [this.heap[index2],this.heap[index1]];
  }
    
    peek(){
    return this.heap[0];
  }
  
  size(){
    return this.heap.length;
  }
}
class MinHeap extends Heap{

  //아이템 추가시에 맨아래에서 부터 오름차순 정렬 검사
  bubbleUp(){
    let currIdx = this.heap.length - 1;
    let parentIdx = Math.floor((currIdx - 1) / 2);
    
    while(this.heap[parentIdx] !== undefined && this.heap[parentIdx][1] > this.heap[currIdx][1]){
      this.swap(currIdx,parentIdx);
      currIdx = parentIdx;
      parentIdx = Math.floor((currIdx - 1) / 2);
    }
  }
  
  //아이템 삭제시에 루트부터 시작해서 오름차순 정렬 검사
  bubbleDown(){
    let currIdx = 0;
    let leftIdx = (currIdx * 2) + 1;
    let rightIdx = (currIdx * 2) + 2;

    if(this.heap[leftIdx] == undefined) return;
    if(this.heap[rightIdx] == undefined) {
      if(this.heap[leftIdx][1] < this.heap[currIdx][1]){
        this.swap(leftIdx,currIdx);
      }
      return;
    }
      
    while( this.heap[currIdx][1] > this.heap[leftIdx][1] || this.heap[currIdx][1] > this.heap[rightIdx][1]){
      let smallerIdx = leftIdx;
      if(this.heap[leftIdx][1] > this.heap[rightIdx][1]){
        smallerIdx = rightIdx;
      }
      this.swap(currIdx,smallerIdx);
      currIdx = smallerIdx;
      leftIdx = (currIdx * 2) + 1;
      rightIdx = (currIdx * 2) + 2;
      
      if(leftIdx >= this.size() - 1 ) break;
    }
  }
  
  add(item){
    this.heap[this.heap.length] = item; //아이템을 추가함
    this.bubbleUp();
  }
  
  poll(){
    let item = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.bubbleDown();
    
    return item
  }
}

let minHeap = new MinHeap();
let len = jobs.length;
jobs.sort((a,b) => a[0] - b[0]); //들어오는 시간 순대로 오름차순 정렬함
//일단 먼저 들어온 작업을 처리하다가 작업 처리중에 들어온 작업들은 소요시간이 작은 애들 먼저 수행할 것임
//시간을 time으로 두고 1초씩 증가시키다가 현재 time에 들어오는 작업을 최소힙에 넣어두고 이전의 작업이 끝나면 최소힙에 들어있는 작업중 가장 작은 작업을 뽑아서 진행. 

let currTime = 0;
let completeTime = 0;
let totalTime = 0;

while( jobs.length > 0 || minHeap.size() > 0){
  
    while( jobs.length > 0){
      if( jobs[0][0] === currTime ){
      minHeap.add(jobs.shift());
      }else break;
    }  
  
    if(minHeap.size() > 0 && currTime >= completeTime){
      let task = minHeap.poll();
      completeTime = task[1] + currTime;
      totalTime += completeTime - task[0];
    }
    
    currTime ++;
}

return Math.floor(totalTime/len)

}