[JAVA] 디스크 컨트롤러

문제 설명

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

예를들어

- 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 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예jobsreturn

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

9

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

---

풀이 방법

일단 이러한 유형의 문제를 Job Scheduling이라고 한다.

Job Sechduling 문제에서 ATT(Average Turnaroung Time)이 가장 작아지는 스케줄링 알고리즘이 SJF(Shortest Job First)라고 한다. 그렇게 하기위해 PriorityQueue가 필요한 것이다..!

따라서 각 시점에서 실행할 수 있는 작업 중 가장 빨리 끝나는 작업을 택하면 된다..!(현재 실행해라 수 있는 작업이란, 현재 시점보다 작업 요청 시점이 이른 작업을 말한다.)

1. 즉 요청시간부터 종료까지 가장 짧게 배치하기 위해서 작업의 소요 시간이 짧은(작은)작업부터 처리해야 한다.
2. 무작정 작업 요청 시점이 짧은 것(작은 것)으로 정렬하는 게 아니라, 하나의 작업이 끝나는 시점까지 들어온 요청에 대해 가장 짧은 수행 시간을 가진 작업을 선택해야 한다.

일단, 작업이 요청되는 시점을 정렬해주고, Queue에 들어오는 작업에서 소요시간이 짧은 것부터 처리해야 한다..! 

 

[변수 설정]
answer : 각 작업의 요청부터 종료까지 걸린 시간을 모두 더한 것
end : 각각의 작업이 수행되서 종료된 시점 (사진에서는 숫자 그래프)
jobsIdx : jobs 배열의 인덱스
done_jobs : 수행된 작업 개수 == 끝난 작업 개수

[2차원 배열 오름차순으로 만들기]

Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); 
Arrays.sort(jobs, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);​

[우선 순위 큐 오름차순으로 만들기]

PriorityQueue<int[]> process = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

• 우선순위 큐는 기준이 있어야 하기 때문에 기준 없으면 오류 삐빅

 

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int end = 0;         // 수행되고 난 직후의 시간
        int jobsIdx = 0;     // jobs 배열의 인덱스
        int done_jobs = 0;   // 수행된 작업 갯수
        
        // jobs 요청시간 오름차순
        Arrays.sort(jobs, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);

        // jobs 처리시간 오름차순 우선순위 큐
        PriorityQueue<int[]> process = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        
        // 요청이 모두 수행될 때까지 반복
        while (done_jobs < jobs.length) {
            // 하나의 작업이 완료되는 시점(end)까지 들어온 모든 요청을 큐에 넣음
            while(jobsIdx < jobs.length && jobs[jobsIdx][0] <= end) {
                process.offer(jobs[jobsIdx++]);
            }
            
            // 큐가 비어있으면 작업 완료(end) 이후에 다시 요청이 들어온다는 의미
            // 작업이 끝나기 전(end 이전) 들어온 요청 중 소요 시간이 짧은 요청부터 수행
            if(!process.isEmpty()) {
                int[] temp = process.poll();
                answer += temp[1] + end - temp[0];
                end += temp[1];
                done_jobs++;
            }
            // (end를 요청의 가장 처음으로 맞춰줌), 즉 다음 작업 요청 시점으로 갱신
            else end = jobs[jobsIdx][0];
        }
        
        return answer/jobs.length;
    }
    
}

[풀이 과정]

1. 첫 번째 while 문 jobsIdx가 0, end가 0
   • while문 안에서 jobs[jobsIdx][0]은 [0,3] 이다. 그리고 jobsIdx++가 되면 while문의 두 번째 조건(job[jobsIdx][0]:1 <= end:0)에 만족하기 못하고 탈출한다.
   • 이 때 process 우선순위 큐에는 [0,3]이 추가된다.
2. Queue가 비어있지 않으면 처리해야 할 요청이 있다는 뜻으로 if문 안으로 들어가게 된다. 들어올 요청 중(queue안에서) 소요 시간이 짧은 것(작은 것)부터 수행한다.
   1. queue안에 있는 첫 번째 값[0,3]을 꺼내고 temp에 넣는다. 
   2. answer에는 0 += 3 + 0 - 0 , end에는 0 += 3 이 , done_jobs++ 
3. 그래서 첫 번째 while문 결과, jobsIdx는 1, end는 3, answer은 3이다.

 

1. 두 번째 while 문 jobsIdx가 1, end가 3
   1. while문 안에서 jobs[jobsIdx][0]은 1과 2 jobsIdx++ 마지막에는 3이되면서 while문의 첫 번째 조건에 만족하지 못하고 탈출한다.
   2. 이 때 process 우선순위 큐에는 [1,9]와 [2,6]이 추가된다.
2. if문 안으로 들어가면서 소요 시간이 짧은 것 부터 수행한다. 즉 9와 6중에 6이 더 작기 때문에 temp에는 [2,6]이 들어가게 된다.
   
   • answer에는 3 += 6 + 3 - 2, end에는 3 += 6 이, done_jobs++
3. 그래서 두 번째 while문 결과, jobsIdx는 3, end는 9, answer은 10 이다. 

 

1. 세 번째 while 문 jobsIdx가 3, end가 9 
   1. while문의 첫 번째 조건에 만족하지 못하기 때문에 while문은 돌아가지 않는다. 
   2. 이때 process 우선순위 큐에는 [1,9]만 남게 된다.
2. if문 안으로 들어가면서 소요 시간이 짧은 것 부터 수행한다. 현재 queue에는 [1,9]만 남아있기에 temp에는 [1,9]만 들어가게 된다.
   1. answer에는 10 += 9 + 9 - 1, end는 9 += 9이, done_jobs++
3. 그래서 세 번째 while문 결과 answer은 27이다. 
4. 요청이 모두 수행됐기에 answer를 jobs.length로 나누면 평균을 구할 수 있다.

---

• 문제를 보고 이해는 갔지만 이것을 어떻게,, PriorityQueue를 이용해서 풀까.. 다른 사람 풀이를 봐도 이해가 안되서 하나하나씩 코드를 분석했다..
• 2차원 배열 오름차순 정렬 알게되었고,, 아직 멀었구나..를 많이 느낀다.. 다시 풀어봐야겠다...