[programmers] 디스크 컨트롤러

문제
https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

 

---

< 디스크 컨트롤러 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	public int solution(int[][] jobs) {
		int answer = 0;

		Arrays.sort(jobs, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[2] == o2[2]) {
					if (o1[1] == o2[1]) {
						return o1[0] - o2[0];
					}
					return o1[1] - o2[1];
				}
				return o1[2] - o2[2];
			}
		});

		int idx = 0, time = 0;

		while (idx < jobs.length) {
			while (idx < jobs.length && time >= jobs[idx][0]) {
				queue.add(new int[] { idx, jobs[idx][0], jobs[idx][1] });
				idx += 1;
			}
			if (queue.isEmpty()) {
				time = jobs[idx][0];
				while (idx < jobs.length && time >= jobs[idx][0]) {
					queue.add(new int[] { idx, jobs[idx][0], jobs[idx][1] });
					idx += 1;
				}
			}
			int job[] = queue.poll();
			if (time < job[1]) {
				time = job[1] + job[2];
			} else {
				time += job[2];
			}
			answer += time - job[1];
		}

		while (!queue.isEmpty()) {
			int job[] = queue.poll();

			if (time < job[1]) {
				time = job[1] + job[2];
			} else {
				time += job[2];
			}
			answer += time - job[1];
		}

		answer /= jobs.length;

		return answer;
	}
}

 

jobs를 작업의 요청 시각이 빠른 순으로 정렬한다. 우선순위 큐를 작업의 소요 시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 정렬하도록 선언한다. 모든 작업이 수행되도록 다음 과정을 반복한다.

 

1. 현재 시간보다 작업 요청 시각이 빠른 작업들을 우선순위 큐에 추가

2. 현재 시간에 요청된 작업이 없어 우선순위 큐가 비어있다면 현재 시간 업데이트 및 우선순위 큐에 추가

3. queue poll

4. 현재 시간 업데이트 및 요청 작업의 반환 시간을 구해 answer에 더하기

 

만약 우선순위 큐에 작업이 남아있다면 위의 3~4번을 반복해 준다. 최종 answer의 값을 jobs의 길이로 나눈 값을 반환한다.

 

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges