프로그래머스[Level 3] 디스크 컨트롤러

문제

링크

풀이

class MinHeap {
    constructor() {
        this.heap = [ null ];
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    getMin() {
        return this.heap[1] ? this.heap[1] : null;
    }
    
    swap(a, b) {
        [ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
    }
    
    insert(value) {
        this.heap.push(value);
        let curIdx = this.heap.length - 1;
        let parIdx = (curIdx / 2) >> 0;
        
        while(curIdx > 1 && this.heap[parIdx][1] > this.heap[curIdx][1]) {
            this.swap(parIdx, curIdx)
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }
    
    pop() {
        const min = this.heap[1];	
        if(this.heap.length <= 2) this.heap = [ null ];
        else this.heap[1] = this.heap.pop();   
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1; 
        
        if(!this.heap[leftIdx]) return min;
        if(!this.heap[rightIdx]) {
            if(this.heap[leftIdx][1] < this.heap[curIdx][1]) {
                this.swap(leftIdx, curIdx);
            }
            return min;
        }

        while(this.heap[leftIdx][1] < this.heap[curIdx][1] || this.heap[rightIdx][1] < this.heap[curIdx][1]) {
            const minIdx = this.heap[leftIdx][1] > this.heap[rightIdx][1] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
            
            if(leftIdx >= this.size()) break;
        }

        return min;
    }
}
function solution(jobs) {
  const length = jobs.length;
  const minHeap = new MinHeap();
  jobs.sort((a,b) => a[0]-b[0]);
  
  let time = 0; // 현재시간
  let complete = 0; // 각 작업이 끝나고 난뒤의 시간 3, 11,17 이런 값들
  let total = 0;
  
  while(1) {
      
    // 모든 요소가 사용되면 종료.
    if(!jobs.length && !minHeap.size()) break;
      
    // jobs의 시작시간이 현재 시간과 같으면 heap에 넣어둔다.  
    while(jobs.length && jobs[0][0] === time) {
        minHeap.insert(jobs.shift());
    }
    
    // 힙에 요소가 있고 현재시간이 작업이 끝난 뒤의 시간 이상이라면
    // 즉, 다음 작업을 실행할 수 있다면
    if(minHeap.size() && time >= complete) {
      const task = minHeap.pop();
      complete = task[1] + time;
      total += complete - task[0];
    }
      
    // 현재시간이기 때문에 1씩 흐르게한다.
    time++;
  }
  
  return total / length >> 0;
}

힙을 이용한 문제이지만, 그냥 단순히 배열을 만들어서 작업시간이 빠른 순으로 정렬한다면 굳이 필요는 없다.

하지만 힙의 내용을 복습도 하고 주어지는 입력에 맞게 기존에 짜둔 힙 코드를 수정하는 연습도 할 수 있어서 사용했다.

이 문제에서 사용된 최소힙은 단순히 정렬이 아닌 작업시간이 최소가 되는 요소를 앞으로 둬야하기에 [1]를 추가해야했다.
원래 코드와 비교하면 수정된 부분을 알 수 있을 것이다.

로직은 다음과 같다.

현재시간을 설정하고, 현재시간과 비교하여 같은 시작시간을 가진 요소를 최소힙에 넣고 작업을 실행한다. 작업이 실행된 뒤에는 complete라고 하는 변수에 작업이 실행되고 난 뒤의 시간을 기록하는데 이 변수가 포인트가 된다. 왜냐하면 현재 시간과 비교하여 complete가 더 크다면 작업을 실행하지 않기 때문이다. 예를 들어 좀 더 자세히 설명했겠다.

[0,3], [1,9], [2, 6]

이 요소들을 시작시간 순으로 최소힙에 들어갈 것이기 때문에 적혀있는 순서대로 들어간다. 근데 들어가는 순서가 작업 순서가 되지 않는다.

[0,3]이 힙에 들어가고, complete는 3이 된다.

현재시간이 1이되고 2가 됨에 따라 [1,9], [2, 6] 힙에 들어간다. 하지만 작업은 실행되지 않는다.
왜냐면 아직 현재시간이 complete를 넘지 못했기 때문이다.
현재시간이 3이되는 시점에서 최소힙의 정렬에 따라 [2,6]이 실행이 되고, complete는 9가된다. 계속 시간이 흘러 9가 됐을 때, [1,9]가 실행이 되고 모든 요소가 사용되어 작업이 종료된다.

설명이 길었지만 포인트는 최소힙의 요소들은 작업소요시간을 기준으로 정렬된다는 것이다.