[프로그래머스] 디스크 컨트롤러::알고리즘

출처 : Programmers(https://programmers.co.kr/learn/courses/30/lessons/42627)

 

 

 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다.

 디스크 컨트롤러는 여러 가지 방법으로 구현할 수 있습니다.

 

 먼저, CPU 프로세스 스케줄링의 여러 가지 방법을 알아보려면 -> https://junboom.tistory.com/13

 

 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 방법(FIFO: First In First Out, A -> B -> C)입니다.

 

< A, B, C 작업의 초기 요청 현황 >

< 순서대로 처리하는 일반적인 방법 >

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

 

 하지만 하드디스크 작업이 끝난 후 가장 짧은 작업 먼저 처리할 경우(SJF: Short Job First, A -> C -> B),

 

< SJF로 처리하는 방법 >

 걸린 시간의 평균은 (3 + 7 + 17) / 3 = 9ms입니다.

 FIFO로 처리했을 때보다 SJF로 처리했을 때 평균 걸린 시간이 더 줄어들게 되는 것을 볼 수 있습니다.

 

 걸린 시간의 평균의 소수 자리는 버리고, SJF로 처리할 때의 평균 시간을 구하는 문제입니다.

---

 일단, 작업의 처리 시간을 오름차순으로 정렬하는 우선순위 큐(PriorityQueue)를 만듭니다(아직 삽입 x).

 정렬되지 않은 작업들(jobs)을 요청이 들어온 순서대로 정렬합니다(Arrays.sort() 부분).

 

 정렬된 작업을 보면서 작업을 시작할 수 있는지 확인합니다.

 

 시작할 수 있는 작업이 있다면 해당 작업을 처리합니다.

 시작할 수 있는 작업이 없다면 해야 할 작업 중 가장 먼저 해야 할 작업의 요청 시간으로 현재 시간을 바꾸고, 큐에 삽입합니다.

 

 더 이상 작업할 것이 없을 때까지 반복하며 이후 평균 시간을 구해 return 합니다.

 

 

Java 코드

 

import java.util.*;

public class Solution_디스크컨트롤러 {
	
	public static int solution(int[][] jobs) {
		int answer = 0;
		int len = jobs.length;
		int time = 0;
		int idx = 0;
		Queue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
		
		Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
		
		while (idx < len || !q.isEmpty()) {
			while (idx < len && jobs[idx][0] <= time)
				q.offer(jobs[idx++]);
			
			if (q.isEmpty())
				time = jobs[idx][0];
			else {
				int[] job = q.poll();
				answer += time - job[0] + job[1];
				time += job[1];
			}
		}
		
		return answer / len;
	}
	
	public static void main(String[] args) {
		System.out.println(solution(new int[][] { {0, 3}, {1, 9}, {2, 6} }));
	}

}