문제 해석
•
예시로 제공된 수식을 살펴보면 {{0, 3}, {1, 9}, {2, 6}} 가 입력될 것인데 이 작업이 어떻게 정렬되야 가장 빠를지를 결정짓는 문제이다.
•
이것은 각 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하는 것이 목표
•
SJF(Shortest Job First) 스케줄링 알고리즘
•
이는 PriorityQueue로 우선순위 큐가 사용된다.
•
processQueue라는 변수명으로 PriorityQueue객체를 만들어서 작업을 넣는데, 우선순위 큐를 통해 jobs[i][j]에서 j=1의 값들에 따라서 작은값들이 유리한것으로 보여졌다.
•
따라서 각 작업의 1인덱스(두번째값)이 작은순서로 정렬될 필요가 있었다.
문제 풀이
•
우선 프로세스 순서인 0번째 인덱스별로 정렬하고
•
Arrays.sort(jobs, (a, b) -> a[0] - b[0])에서 a[0] - b[0]은 작업의 요청 시간을 기준으로 오름차순 정렬하도록 하는 부분입니다.
•
따라서 배열을 처음에 {0, 3}, {1, 9}, {2, 6} 순서대로 정렬하고 우선순위 큐에 저장됩니다.
◦
continue;를 통해서 아직 빼내는 작업은 실행되지 않습니다.
•
큐에 저장되고있는 작업들은 우선순위 큐는 두번째 인덱스인 [1]에 따라 내림차순으로 정렬됩니다.
◦
일반 Queue였으면 {0, 3}, {1, 9}, {2, 6} 순서로 저장되었겠지만, 정렬조건을 추가해두었기 때문에
◦
{0, 3}, {2, 6}, {1, 9} 순서로 정렬되 있습니다. 따라서 poll로 빼올때마다 이 순서로 추출 됩니다.
◦
이렇게 정렬된 순서대로 작업을 처리함으로써 최적의 평균 시간을 얻을 수 있게 됩니다.
import java.util.Arrays;
import java.util.PriorityQueue;
public class Solution3 {
public int Solution3(int[][] jobs){
Arrays.sort(jobs, (a, b) -> a[0] - b[0]); // 주어진 작업 배열 jobs를 작업의 요청 시간인 a[0]을 기준으로 오름차순 정렬합니다.
// processQueue를 만들어서 작업을 넣는데, 우선순위 큐를 통해 jobs[i][j]에서 j=1의 값들에 따라서 작은값들이 유리함.
//우선순위 큐인 processQueue를 생성. 이 큐는 작업의 소요 시간인 a[1]을 기준으로 오름차순으로 정렬
PriorityQueue<int[]> processQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 소요 시간 오름차순 우선순위 큐
int time = 0; // 현재까지의 시간
int total = 0; // 총 소요 시간
int index = 0; // 작업 배열을 순회하기 위한 인덱스 index
while (index < jobs.length || !processQueue.isEmpty()) {
if (index < jobs.length && jobs[index][0] <= time) {
processQueue.offer(jobs[index]);
index++;
continue;
}
if (!processQueue.isEmpty()) {
int[] job = processQueue.poll();
time += job[1];
total += time - job[0];
} else if (index < jobs.length) {
// 작업큐가 비어있으면서 아직 작업이 남아 있다면,
// 다음 작업의 요청 시간으로 시간을 업데이트
time = jobs[index][0];
}
}
return total / jobs.length; // 평균
}
public static void main(String[] args){
Solution3 sol = new Solution3();
int[][] jobs = {{0,3},{1,9},{2,6}};
System.out.println(sol.Solution3(jobs));
}
}
Java
복사