[programmers/JAVA] 디스크 컨트롤러

문제 설명

문제 링크

접근 방법

평균 시간을 줄이는 방법은, 소요 시간이 작은 순서대로 처리하는 것이다. (운영체제 지식 중 스케줄링 알고리즘이라고 있는데, 그 중 SJF(Shortest Job First) 에 대해 바로 기억을 했다면 좀 더 쉽게 해결할 수 있었을 것 같다. 찾아봤다는 이야기다.) 단 가장 마지막에 작업이 완료된 시간 이전에 들어온 요청임을 확인하여 순서대로 추가한다. 자바에서 특정한 조건에서 원소의 비교를 수행하는 Comparator 를 이용하여, 우선 jobs 를 요청 시점 기준으로 정렬하고, 소요시간이 작은 순서대로 정렬하는 PriorityQueue 를 선언한다. 그 다음 완료 시점보다 앞에서 요청된 작업들을 큐에 넣고, 순서대로 꺼내면서 시간을 구해준다. (종료 시간-요청 시간)+소요 시간 을 구해주면 각 작업의 요청부터 완료까지의 시간을 구할 수 있다. 이렇게 모든 작업의 총 시간을 구해주면 평균도 구할 수 있다.

소스 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, Comparator.comparingInt(e -> e[0]));
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(e -> e[1]));
        int answer = 0, count = 0, endTime = 0, i = 0;
        while (count < jobs.length) {
            while (i < jobs.length && jobs[i][0] <= endTime) priorityQueue.add(jobs[i++]);

            if (priorityQueue.isEmpty()) {
                endTime = jobs[i][0];
            } else {
                int[] current = priorityQueue.poll();
                int requestTime = current[0];
                int duration = current[1];
                answer += endTime + duration - requestTime;
                endTime += duration;
                count++;
            }
        }
        return answer / jobs.length;
    }
}

제출 결과

마무리하며

단순히 힙 만을 사용하는 것이 아닌, 운영체제의 전공적인 지식도 어느정도 요구하는 문제였다.