문제

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

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

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

제한 사항

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

풀이

아이디어

• 최소 힙을 요청시간이 지났지만 실행하지 못하고 대기하고 있는 작업들의 공간으로 규정하고, 최소 힙에서의 우선순위는 해당 작업의 '소요시간'이다.
• 요청순서대로 대기열에 들어가야 하므로 우선 jobs 배열을 요청시간 기준 오름차순으로 정렬한다.
• 마지막 작업이 끝난 시간을 lastFinished, 현재 시간을 time, 요청부터 작업마무리까지 걸린 시간들의 총합을 sum이라고 하자.
• time을 1씩 증가시켜가면서 다음 작업을 수행한다. (1씩 증가시킬 수 있는 이유는 총 500개의 작업이 최대 1,000초 걸리므로 최대 총 500000번 time이 증가되고, 이는 시간복잡도에 큰 영향을 끼치진 않기 때문이다.) 이때, while문의 조건은 heap의 사이즈가 0보다 크거나 jobs의 길이가 0보다 클 때이다. (pop과 shift연산을 하려면 당연히 그래야한다.)
  • 현재시간 time이 jobs 배열에서 요청시간이 가장빠른 작업의 요청시간과 같아졌다면, 해당 작업을 jobs에서 빼내서 최소 힙에 넣는다. 이때, 요청시간이 같은 작업들이 있을 수 있으므로 while문을 사용하도록 한다.
  • 현재시간 time이 어떤 작업이 끝나는 시간 이후가 된다면, 하드디스크는 또 다른 작업을 수행할 준비가 되었다는 뜻이므로, 대기열에 있는 작업 하나를 pop해서 수행한다. 해당 작업이 끝나는 시간에 맞춰 lastFinished을 업데이트해주고, sum도 업데이트 해준다.
• 모든 과정이 끝났다면, sum을 처음 jobs의 길이만큼 나눠주고 소숫점은 버린 것을 반환한다.

코드

class Heap {
    constructor() {
        this.heap = [null];
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    peek() {
        return this.heap[1];
    }
    
    insert(job) {
        this.heap.push(job);
        
        let curIdx = this.heap.length - 1;
        let parentIdx = Math.floor(curIdx / 2);
        
        while(curIdx > 1 && this.heap[curIdx][1] < this.heap[parentIdx][1]) {
            this.swap(curIdx, parentIdx);
            curIdx = parentIdx;
            parentIdx = Math.floor(curIdx / 2);
        }
    }
    
    heapPop() {
        let ret = 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 ret;
        //오른쪽 자식은 없는데 왼쪽 자식은 남아있다면
        if(!this.heap[rightIdx]) {
            //왼쪽자식과 비교 및 자리찾아가기 수행
            if(this.heap[leftIdx][1] < this.heap[curIdx][1]) {
                swap(leftIdx, curIdx)
            }
            return ret;
        }
        //왼쪽자식, 오른쪽 자식 다 있을 때 할 일: 자식들과 비교하며, 알맞은 위치로 내려가기
        while(this.heap[leftIdx][1] < this.heap[curIdx][1] || this.heap[rightIdx][1] < this.heap[curIdx][1]) {
            let 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 ret;
    }
}

function solution(jobs) {
    //요청시간을 최신순으로 정렬한다.
    jobs.sort((a, b) => a[0] - b[0]);
    
    let heap = new Heap();
    let time = 0;   //현재시간
    let sum = 0;
    let lastFinished = 0;
    let originalLength = jobs.length;
    
    while(heap.size() || jobs.length > 0) {
        //현재 시간과 요청시간이 같은 것들을 대기 힙에 넣어준다.
        while(jobs.length && time == jobs[0][0]) {
            let job = jobs.shift();
            heap.insert(job);
        }
        
        if(heap.size() && time >= lastFinished) {
            let doneTask = heap.heapPop();
            lastFinished = time + doneTask[1];
            sum += lastFinished - doneTask[0];
        }
        
        time++;
    }
    
    return Math.floor(sum / originalLength) ;
    
}

돌아보기

소수점을 버릴 때 Math.floor()보다 비트연산자 >> 0을 사용하는 것이 훨씬 성능이 좋다고 한다.

파이썬 코드

• 파이썬의 heapq 모듈에서 요소가 2개 이상인 원소들이 들어올 때 해당 원소의 첫번째 값을 기준으로 정렬하기 때문에, 이 문제에서처럼 '소요시간'을 기준으로 최소힙을 만든다고 하면 인덱스의 순서를 바꿔서 넣어줘야 한다.
• 마찬가지로 주의할 점은 endTime += process[0]을 하면 안되고, endTime = time + process[0]을 해주어야 한다는 점이다. 왜냐하면, 작업들이 바로바로 실행되는 것이 아니라 좀 휴식기를 가지고 진행될 수도 있기 때문에, 현재 시간 기준으로 process[0]을 더해줘야 틀리지 않는 작업완료시간을 업데이트 할 수 있다.

from collections import deque
from heapq import heappush, heappop

def solution(jobs):
    #일단 들어온 작업요청시간 순서대로 오름차순으로 정렬이 필요함
    jobs.sort(key=lambda x: x[0])
    jobs = deque(jobs)
    heap = []
    answer = 0
    totalTask = len(jobs)
    
    time = 0
    endTime = 0
    
    while len(jobs) or len(heap):
        #현재시간과 같은 요청시간을 가진 작업들을 모두 대기열에 넣기
        #넣을 때는 걸리는 시간이 최소로 들어가게 넣어준다
        while len(jobs) and jobs[0][0] == time:
            nextJob = jobs.popleft()
            heappush(heap, (nextJob[1], nextJob[0]))
    
        #힙에서 작업을 하나씩 빼면서 본다
        while len(heap) and endTime <= time:
            process = heappop(heap)
            endTime = time + process[0]
            answer += endTime - process[1]
        
        time += 1
        
    
    return answer//totalTask