[프로그래머스] LV.3 디스크 컨트롤러 (JS)

문제

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예시

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

풀이

문제 자체의 의도는 운영체제의 SJF(Shortest Job First) 알고리즘 구현과 동일하다. 때문에 해당 알고리즘을 미리 알고 있다면 의도 파악 자체는 굉장히 쉬울 것 이다.

해당 알고리즘을 모르는 사람들을 위해 간략하게 설명하자면, 종료까지 걸리는 평균시간(Average Turnaround time)이 최소가 되기 위해서는 가장 짧은 실행 시간을 가진 Process(해당 문제에선 하드디스크로의 요청)를 먼처 처리하면 된다. 때문에 Greedy 하게 풀 수 있다.

문제풀이의 핵심이 되는 '가장 짧은 실행 시간 요청 부터 처리'가 잘 이해되지 않는다면 SJF 알고리즘에 대해 검색해보는 것을 추천한다.

이때 문제의 제한 사항 중에, '하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 수행'한다는 조건이 있다. 이 조건은 다음과 같이 해석이 가능하다

• 현재 실행 중인 요청이 전무하고, 해당 시점에서 가장 먼저 들어온 요청이 단 1개일 경우 해당 요청을 즉각 수행한다.
• 현재 실행 중인 요청이 있다면 현재 시간이 작업이 요청되는 시점이더라도 해당 요청은 실행하지 않고 대기리스트에 추가된다.
• 실행 중인 요청이 끝났다면, 대기리스트에 존재하는 요청 중에 실행시간이 가장 짧은 요청부터 처리한다.

즉 '먼저 요청이 들어온 작업부터 수행'이라는 의미는 무조건 대기리스트에 먼저 들어온 순으로 실행하라는 의미가 아니다. 마지막 해석이 중요하다. 대기리스트에 존재하는 요청들은 모두 요청 시점에서 바로 실행하지 못했기 때문에 하드디스크가 비어 있는 순간 다 실행할 수 있는 자격이 된다. (문제의 제시 조건이 상당히 애매모호하게 드러나있어 사실 여러 해석이 가능할 것 같다. 다만 해당 문제는 위의 방식으로 풀어야 모든 테스트케이스를 통과할 수 있다.)

따라서 먼저 요청이 들어온 시점 순으로 오름차순 정렬을 한다.
jobs의 최대 길이는 500이고 각 job에서 소요되는 최대 시간은 1000이기 때문에 현재 시간을 0부터 최대값 500 * 1000 = 500000 까지 반복문을 돌려도 시간 복잡도가 크지 않다. 따라서 현재 시간을 저장할 변수 time을 선언하고 해당 값을 1씩 증가시킬 것 이다.

jobs.sort((a, b) => a[0]-b[0]);	// jobs를 요청시점 순으로 오름차순 정렬

time = 0;	// 현재 시간

while (...condition) {
  ...
  time++;
}

사실 해당 문제는 Heap 카테고리에 있긴 하지만 역시 저번 포스팅과 마찬가지로 굳이 Heap을 이용하지 않더라도 통과가 가능하다. 그러나 저번 포스팅에서부터 Heap을 다루었으니 이번 기회에 그냥 Heap을 구현하여 풀어보자. JS를 이용해 HEAP을 구현하는 상세한 과정은 해당 포스팅을 참고하자.

여기서는 최소값 부터 반환하므로 최소힙을 구현했다. 다만 입력되는 값이 배열이기 때문에, 위 포스팅에서 값을 비교하는 부분만 다음과 같이 수정했다.

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] ];
    }
    
  
    heappush(value) {
        this.heap.push(value);
        let curIdx = this.heap.length - 1;
        let parIdx = (curIdx / 2) >> 0;
        
        // 원래는 바로 primitive value를 입력받아 this.heap[parIdx] 와 this.heap[curIdx]를 비교했다.
        // 그러나 해당 문제에서 입력을 [요청시점, 실행시간]의 형태로 받을 것이고, 실행시간을 비교해 Heap을 구성할 것이므로 this.heap[pardIdx][1]...과 같이 비교한다.
        while(curIdx > 1 && this.heap[parIdx][1] > this.heap[curIdx][1]) {
            this.swap(parIdx, curIdx)
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }
    
    heappop() {
        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]) {
            // heapppush 에서와 동일한 이슈이다.
            if(this.heap[leftIdx][1] < this.heap[curIdx][1]) {
                this.swap(leftIdx, curIdx);
            }
            return min;
        }

        // heapppush 에서와 동일한 이슈이다.
        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;
    }
}

그렇다면 Heap에 정렬된 jobs 배열의 원소의 값을 삽입하는 시점이 언제일지 생각해보자. 반복문 외부에 현재 시간을 나타내는 time 변수가 있다. 해당 값은 0부터 500000까지 증가하게 될 것이다. 이때 jobs 배열은 요청시점 순으로 오름차순 정렬 시켜주었으므로, 앞에서부터 각 job의 요청시점이 현재 time과 일치하는 순간에 minHeap에 push 하도록 하자. 그렇다면 일종의 대기리스트 역할을 하는 minHeap에는 현재 time에 실행될 수 있는 요청들을 가지게 될 것 이다. 그리고 minHeap에서 pop을 하면 자료구조에 의해 가장 최소값을 가진 root 값이 반환될 것 이다.

...

const minHeap = new MinHeap();

while(...condition) {
  while(jobs.length) {
    if(jobs[0][0] === time)	// 먼저 요청된 순으로 각 job의 요청시점이 현재 time과 일치하다면
      minHeap.heappush(jobs.shift());	// 해당 job을 heap에 push + 원본 배열에서 해당 job 제거
    else break;
  }
  time++'
}

마지막으로 요청부터 종료까지 걸린 시간의 평균을 구해보자. 대기리스트 역할을 하고 있는 minHeap에 값이 존재하고, 현재 time이 어떤 작업이 완료되고 나서의 시점보다 크거나 같다면 우리는 minHeap에서 가장 작은 실행시간을 가진 job 하나를 pop 할 수 있다.

해당 작업이 수행되면서 다음을 구할 수 있다.

• 완료시간 갱신 = 해당 작업의 실행시간 + 현재 시간
• 전체 소요 시간 += 갱신된 완료 시간 - 해당 작업이 요청된 시점

즉 예를 들어, A라는 요청이 0초에 바로 요청되었고, 총 10초간 수행된다고 하고 초기 total(전체 수행시간)과 complete(완료시간)은 각각 0이라고 하자. 해당 작업이 모두 끝나고 완료된 시간은 현재시간(0) + 작업 실행 시간(10) = 10초이다. 그리고 이때 소요된 시간은 완료시간(10) - 작업 요청 시점(0) = 10초가 된다. 이때 B라는 요청이 2초에 요청되었고, 총 6초간 수행된다고 하면 B 요청이 끝나고 완료된 시간은 현재시간(10) + 작업 실행 시간(6) = 16이고 총 소요시간은 기존 소요 시간(10) + 완료시간(16) - 작업 요청 시점(2) = 24가 되는 것을 확인할 수 있다. 이를 코드로 나타내면 아래와 같다.

...
let time = 0;	// 현재시간
let complete = 0;	// 각 작업이 종료될 때의 완료시점
let total = 0;	// 각 작업들이 소요된 시간의 누적합
while(...condition) {
  ...
  
  if(minHeap.size() && time >= complete) {
    const task = minHeap.heappop();
    complete = task[1] + time;
    total += complete - task[0];
  }
  
  time++'
}

핵심 로직은 모두 구현이 끝났다. 반복문이 끝나면 total 변수에 각 요청들이 SJF 알고리즘 방식으로 처리된 실행시간의 누적합이 담겨있을 것이다. 평균값을 반환하므로 total을 jobs 배열의 개수만큼 나누어 주면 된다. 전체 코드는 아래와 같다.

코드

function solution(jobs) {
  const count = jobs.length;
  const minHeap = new MinHeap();
  jobs.sort((a,b) => a[0]-b[0]);
  
  let time = 0;
  let complete = 0;
  let total = 0;
  
  while(jobs.length || minHeap.size()) {
    while(jobs.length) {
      if(jobs[0][0] === time) {
        minHeap.heappush(jobs.shift());
      } else break;
    }
    
    if(minHeap.size() && time >= complete) {
      const task = minHeap.heappop();
      complete = task[1] + time;
      total += complete - task[0];
    }
    time++;
  }
  
  return total / count >> 0;
}

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] ];
    }
    
    heappush(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;
        }
    }
    
    heappop() {
        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;
    }
}

출처

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