디스크 컨트롤러 풀이 (힙, 우선순위 큐 사용)
프로그래머스 Lv 3 문제로 힙을 사용하여 효과적으로 풀 수 있습니다. 하지만 힙을 사용하기 전에 다음을 명확히 하는 것이 좋습니다. 문제에 주어진 예시로 봤을 때 (0, 3), (2, 6), (1, 9) 으로 작업을 처리했을 때 평균 처리시간이 제일 적은 것을 알 수 있습니다. 이로써 도출할 수 있는 포인트는 “겹치는 작업이 있을 때 제일 처리시간이 작은 작업 (대기시간을 적게 하는 방향)”을 기준으로 힙을 활용해야 합니다. 문제 제시 조건으로 “하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.” 이기 때문에 요청 시간이 동일하게 들어오는 경우만 따로 생각해주고(적은 순으로 정렬) 겹치는 부분을 중점으로 알고리즘을 설계했습니다.
그리디 알고리즘의 정당성
다음 그림을 보시면 파란색이 현재 수행중인 작업이고 검정색 선과 주황색 선이 파란색 수행 중 들어온 처리시간이 두개의 다른 작업들 입니다. 총 수행시간을 관점으로 방정식을 세워보면 (9 - 검정색 작업 시작 + 9 - 주황색 작업 시작) 으로 공통적으로 묶이고 각각의 처리시간이 대기시간에 영향을 미친다는 것을 알 수 있습니다. 그리고, 나머지 각각의 수행시간들을 더해 주면 총 수행시간이 됩니다. 따라서, 최소의 처리시간을 우선적으로 처리해주면 됩니다.
알고리즘 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;
class Job implements Comparable<Job>{
int start, time;
public Job(int start, int time){
this.start = start;
this.time = time;
}
@Override
public int compareTo(Job o){
return this.time - o.time;
}
}
class Solution {
public int solution(int[][] jobs) {
int length = jobs.length;
int answer = 0;
Arrays.sort(jobs, (a, b) -> {
if(a[0] == b[0]){
return a[1] - b[1];
} else return a[0] - b[0];
});
int index = 1;
int curTime = jobs[0][0] + jobs[0][1];
int total = jobs[0][1];
PriorityQueue<Job> pq = new PriorityQueue<>();
while(index < length || !pq.isEmpty()){
if(index < length && jobs[index][0] <= curTime){
pq.offer(new Job(jobs[index][0], jobs[index][1]));
index++;
continue;
}
if(!pq.isEmpty()){
Job next = pq.poll();
total += curTime - next.start + next.time;
curTime += next.time;
} else {
curTime = jobs[index][0] + jobs[index][1];
total += jobs[index][1];
index++;
}
}
return total / length;
}
}