[프로그래머스(Programmers)][자바(java)] (Lv3) 디스크 컨트롤러

 

programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

 

문제 풀이

 

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

public class Solution {

	static class Job {
		int requestTime, workingTime; // 요청 시각, 작업 시간
		Job(int requestTime, int workingTime) {
			this.requestTime = requestTime;
			this.workingTime = workingTime;
		}
	}

	public static int solution(int[][] jobs) {
		int sum = 0, n = jobs.length, i = 0, startTime = 0, endTime = 0, totalTime;
		Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); 												// 요청 시각 오름차순
		PriorityQueue<Job> pq = new PriorityQueue<>((o1, o2) -> o1.workingTime - o2.workingTime);	// 작업 시간 오름차순
		while (i < n || !pq.isEmpty()) {
			while (i < n && jobs[i][0] <= startTime) {
				pq.add(new Job(jobs[i][0], jobs[i][1]));
				i++;
			}
			if (pq.isEmpty())
				startTime = jobs[i][0]; 				// 시작 시각
			else {
				Job job = pq.poll();
				endTime = startTime + job.workingTime; 	// 종료 시각 = 시작 시각 + 작업 시간
				totalTime = endTime - job.requestTime;	// 소요 시간 = 종료 시각 - 요청 시각
				sum += totalTime;
				startTime = endTime; // 다음 시작 시각 = 현재 종료 시각
			}
		}
		return sum / n;
	}
}

 

*  우선순위 큐 -- 최소 힙

-  작업의 요청부터 종료까지 걸린 시간의 평균이 가장 작은 것을 구하는 문제
-  작업의 요청 시간을 기준으로 오름차순 정렬
-  작업의 소요 시간을 기준으로 더 작은 값이 먼저 나오는 우선순위 큐 생성 
-  현재 시작 시간보다 먼저 요청된 작업들을 미리 우선순위 큐에 넣고 하나씩 빼며 총 시간( 종료시간-요청시간 )들을 더하고 평균을 구함 

 

              ex)  int jobs[][] = { {0, 3}, {1, 9}, {2, 6} }