문제 설명
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
예를들어
- 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 | return |
|---|---|
| [[0, 3], [1, 9], [2, 6]] | 9 |
입출력 예 설명
문제에 주어진 예와 같습니다.
0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.
문제를 이해하는데에는 어렵지 않았으나, 구현함에 있어 놓친 부분이 있었다.
- 요청이 들어온 순서대로 작업이 실행되지 않고, 수행시간이 적은 순서대로 작업이 수행되어야 평균 소요시간이 적게 나오는구나라고 착각한 것
- 무조건 수행시간이 적은 순서대로 작업을 수행할 수 없는 이유
[{0,3},{2,9},{50,6}]
이렇게 되어 있으면 3초 후, 두번재 작업을 시작해야하는데 3번째 작업이 소요시간이 더 적기 때문에 50초까지 기다리고 3번째 작업을 수행한 후, 두번째 작업을 수행하게 된다.
중요한건, 시간의 개념을 변수에 집어넣어 해당 시점에, 작업요청이 들어온 것들을 우선순위큐에 넣어주는 작업이 필요하다.
그 이후에 해당 노드에서 소요시간이 적은 것부터 처리하면된다.
//요청시간[0] 기준 오름차순 정렬
Arrays.sort(jobs, (((o1, o2) -> o1[0] - o2[0])));멋있다. 람다식
해석을 해보자면 o1[0]부분을 jobs의 {0,3}에서 앞의 0을 나타내는 부분이다. 요청시점을 나타내는 값을 기준으로 오름차순 정렬을 한다는 뜻.
그 이유는 요청시점을 기준으로 정렬하여 시간의 흐름에 따라 작업을 추가할 것이기 때문이다.
//시간의 흐름에 따라 요청이 들어온 jobs만 추가가
while (cnt < jobs.length && jobs[cnt][0] <= time) {
minHeap.add(jobs[cnt]);
cnt++;
}이렇게 시간이라는 변수를 두고, 시간과 jobs[cnt][0] 즉, 작업요청시간을 비교하여 해당 시점까지 요청된 작업만 우선순위 큐에 넣는다.
PriorityQueue<int[]> minHeap = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));우선순위큐는 최소값 우선순위로 선언하여, 이번엔 o1[1], 그러니까 jobs의 {0,3} 부분에서 3을 나타내는부분, 즉 해당작업의 소요시간을 나타내는 값을 말한다. 소요시간을 기준으로 최소값 우선순위큐를 만들겠다 이 말이다.
이제 시간 계산을 해보면
해당 작업요청으로부터 총 소요시간이라는 것은,
작업요청시간에서 부터 작업완료까지이다.
jobs[i][0] 에서 부터 작업완료까지인데,
작업완료는 이전 작업이 언제 끝났냐 그리고 언제 시작하냐에 따라 다르기 때문에 끝나는 시간을 잘 구해야한다.
우선, 작업요청시간을 start 변수에 넣어준다.
int start = minHeap.peek()[0];그리고 최소값 우선순위큐의 Root 값을 poll(); 해주고(큐에서 값을 빼낸다. 큐에는 해당 값이 남아있지 않다.) 작업소요시간을 period 변수에 넣는다.
int period = temp[1];이제, 작업을 시작한 시점 + 작업소요시간 = 작업완료시간
이다.
시점은 time으로 해당 시점을 지정할 것이고,
작업 소요시간은 period.
따라서 end = time + period
int end = time + period;time++로 구현하며 1초 1초 구간을 만지다 깨달았다. 작업 완료 시점으로 바로 보내도 된다는 것을 작업을 시작했으면 끝날때까지 while문이 헛돌게 된다.
time을 작업 완료시점으로 옮겨준다. 작업하는 시간동안은 따로 로직이 필요없으니
time = time + period;
int end = time;그리고 작업완료시점 - 작업 요청시점 = 우리가 원하는 값이다.
int term = end - start;answer 변수에 차곡차곡 모아준다.
answer += term;다음과 같이 완성된다.
int start = minHeap.peek()[0];
int[] temp = minHeap.poll();
int period = temp[1];
time = time + period;
int end = time;
int term = end - start;
answer += term;
fin++;
허나 이렇게 하면 어떤 문제가 발생하는가 보니,
[{0,3},{10,9},{50,6}]
이렇게 될 시에 3초~10초까지는 요청받은 작업이 아무것도 없어
3초 이후에 heap에 들어온 데이터가 아무것도 없이 텅 비게된다.
즉 위 로직의
int start = minHeap.peek()[0];
int[] temp = minHeap.poll();맨 위 시작부분이 그냥 null이 리턴되며 아무 진전이 없게된다.
while문은 무한히 돌아간다.
그래서 만약 heap이 비어있다면, 요청시점순으로 정렬한 jobs의 다음 작업 요청시점으로 시점을 옮겨준다.
if(!minHeap.isEmpty()) {
//작업 시간 구하는 위에 설명한 로직
}else{
time = jobs[cnt][0]; //다음 작업요청 시점
}여기서 하나만 더, 이렇게 함수를 돌리면 while(true) {}로 무한대로 돌릴 수 없으니 언제 while을 끊을 것인지 생각해본다.
아마도 모든 작업을 마쳤을 때일 것인다.
작업시간 구하는 로직 맨 아래에 변수 하나를추가하여 ++ 해주고, 그 값은 작업 완료시마다 1만큼씩 커지는 값이 된다.
모든 작업 완료시 while문을 그만 돌아라 하려면
while(변수<jobs.length)하면 된다.
따라서 나는 fin이라는 변수를 두고 ++해주었다.
while (fin < jobs.length) {
//시간의 흐름에 따라 요청이 들어온 jobs만 추가가
while (cnt < jobs.length && jobs[cnt][0] <= time) {
minHeap.add(jobs[cnt]);
cnt++;
}
if(!minHeap.isEmpty()) {
int start = minHeap.peek()[0];
int[] temp = minHeap.poll();
int period = temp[1];
time = time + period;
int end = time;
int term = end - start;
answer += term;
fin++;
}else{
time = jobs[cnt][0];
}
}
마지막으로, 리턴시에 소수점은 버리라 했으나 애초에 answer는 int 타입이니 노상관으로 리턴시킨다.
public static int solution(int[][] jobs) {
int answer = 0;
int cnt = 0;
int time = 0;
//요청시간[0] 기준 오름차순 정렬
Arrays.sort(jobs, (((o1, o2) -> o1[0] - o2[0])));
PriorityQueue<int[]> minHeap = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));
int fin=0;
while (fin < jobs.length) {
//시간의 흐름에 따라 요청이 들어온 jobs만 추가가
while (cnt < jobs.length && jobs[cnt][0] <= time) {
minHeap.add(jobs[cnt]);
cnt++;
}
if(!minHeap.isEmpty()) {
int start = minHeap.peek()[0];
int[] temp = minHeap.poll();
int period = temp[1];
time = time + period;
int end = time;
int term = end - start;
answer += term;
fin++;
}else{
time = jobs[cnt][0];
}
}
return answer / jobs.length;
}