프로그래머스 - 디스크 컨트롤러

1. 문제

문제 링크

2. 풀이

2-1. 조건

문제에서 요구한대로 작업들이 어떻게 효율적으로 처리되어야 할지 생각해봅시다.
기본적으로 요청 시간이 가장 빠른 순서대로 처리를 하되,
하나의 작업을 끝내고 난 후 그 안에 요청된 다른 작업들이 있다면
작업 시간이 짧은 순서대로 처리를 해줘야합니다.

문제의 예시를 들어 설명하자면
기본적으로 [0, 3] [1, 9] [2, 6] 순서대로 처리합니다.
1번 작업이 끝나고 난 후의 시간은 3ms인데
3ms 안에 요청된 작업들은 2, 3번 작업 모두 해당하니까
[1, 9] [2, 6] 순서가 아닌 [2, 6] [1, 9] 순서대로 처리를 해줘야
문제에서 요구하는 스케줄링을 구현할 수 있습니다.

이를 구현하기 위한 계획은 다음과 같습니다.

1. 작업들을 요청 시간순대로 정렬합니다.
2. 작업이 완료되는 시점까지 요청이 들어온 작업들을 우선순위큐에 모두 넣습니다.
3. 우선순위큐에 들어온 작업이 없다면 작업과 작업 사이에 텀이 존재한다는 의미이므로
   작업이 완료되는 시점을 다음에 요청이 들어올 작업의 시간으로 맞춰줍니다.
4. 우선순위큐에 들어온 작업이 있다면 작업 시간이 가장 짧은 작업을 빼서 작업을 진행시킵니다.
5. 3, 4를 반복해서 모든 작업을 완수합니다.

3. 전체 코드

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
		int sum = 0; // 작업들의 요청부터 완료 시간까지의 합
		int timeOfJobEnded = 0; // 한 작업의 끝나는 시간
		int jobIndex = 0; 
		int resolveCount = 0;
		
		// 1. 작업들을 요청 시간순대로 정렬합니다.
		Arrays.sort(jobs, (job1, job2) -> job1[0] - job2[0]);
		
		// 요청 시간이 짧은 순대로 작업을 정렬하는 우선순위큐
		PriorityQueue<int []> waitQ = new PriorityQueue<>((job1, job2) -> job1[1] - job2[1]);
		
		// 5. 3, 4를 반복해서 모든 작업을 완수합니다.
		while (resolveCount < jobs.length) {
			// 2. 작업이 완료되는 시점까지 요청이 들어온 작업들을 우선순위큐에 모두 넣습니다.
			while (jobIndex < jobs.length && jobs[jobIndex][0] <= timeOfJobEnded) {
				waitQ.add(jobs[jobIndex++]);
			}
			
			// 3. 우선순위큐에 들어온 작업이 없다면 작업과 작업 사이에 텀이 존재한다는 의미이므로 
			// 작업이 완료되는 시점을 다음에 요청이 들어올 작업의 시간으로 맞춰줍니다.
			if (waitQ.isEmpty()) {
				timeOfJobEnded = jobs[jobIndex][0];
				continue;
			}
			
			// 4. 우선순위큐에 들어온 작업이 있다면 작업 시간이 가장 짧은 작업을 빼서 작업을 진행시킵니다.
			int[] job = waitQ.poll();
			
			timeOfJobEnded += job[1];
			sum += timeOfJobEnded - job[0];
			resolveCount++;
		}
		
		return (int)Math.floor(sum / jobs.length);
    }
}