[Heap] 디스크 컨트롤러 - Java코드 ★★★

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

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

 

문제

 

이해

반가운 개념이 나타났다. (OS시간에 배웠던 SJF 방식)

입력으로 작업의 요청시간과 수행시간이 들어온다.

가장 짧은 Job부터 스케줄링하면 각각의 Job이 요청시간으로부터 대기시간과 수행종료 시점까지의 시간의

총 평균시간이 가장 짧은 스케줄링 기법이다.

 

해당 기법을 Java로 짜보는건 처음이지만,

Heap을 이용해 정렬된 요청시간과 대기시간을 기준으로  

SJF를 구현하여 가장 짧은 평균수행시간을 구해보자

 

 

풀이

 

Class와 Comparable을 정의하여 우선순위큐를 이용하는 방법

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

class Solution {
    public static int solution(int[][] jobs) {        // 요청시간, 수행시간
        Arrays.sort(jobs, Comparator.comparingInt(o->o[0])); // 요청시간순으로 정렬
        PriorityQueue<Disk> pq = new PriorityQueue<>(); // Disk 객체 주입시 ,실행시간 순으로 삽입
        int totalTime = 0;		// 지금까지 총 걸린시간
        int finished = 0;  		// 지금 까지 일이 끝난 disk갯수
        int currentTime = 0;		// 현재시간
        int diskIndex = 0;		// queue에 들어간, 시작시간이 현재시간보다 이상이여서
        while(finished < jobs.length) {
            while (diskIndex < jobs.length && jobs[diskIndex][0] <= now) { // 현재시간에 수행가능한 Job을 넣어준다
                pq.add(new Disk(jobs[diskIndex][0], jobs[diskIndex][1]));  // 수행가능 Job을 추가
                diskIndex++;
            }
            if(pq.isEmpty()){ // 현재시간에 수행시킬 Job이 없으면
                now = jobs[diskIndex][0]; // 현재시간을 다음 Job 요청시간으로 갱신
            }else{ // 수행가능한 Job들을
                Disk disk = pq.poll(); // 짧은 Job부터 하나씩 빼서
                total += disk.duration + (now - disk.startTime); // 전체소요 시간 추가
                now += disk.duration; // 현재시간 갱신
                finished++;
            }
        }
        return total / jobs.length;
    }
    // 내부 정적 클래스
    private static class Disk implements Comparable {
        int startTime;
        int duration;

        public Disk(int startTime, int duration) {
            this.startTime = startTime;
            this.duration = duration;
        }

        @Override
        public int compareTo(Object o) {
            Disk d = (Disk) o;
            return duration - d.duration; // 수행시간 순으로 정렬되도록
        }
    }
}

클래스에서 정렬방식을 믹스인하는 Comparable을 구현해주어도 되며,

PriorityQueue<Disk> pq = new PriorityQueue<>(((o1, o2) -> o1.duration - o2.duration));

이렇게 힙을 생성함과 동시에 Comparable을 구현해도된다.

 

기존의 Jobs는 요청시간별로 정렬해주고

while문을 돌면서 현재시간과 비교해가면서, 현재 수행가능한 Job들을 힙에 넣어준다.

 

만약 아무것도 힙에 들지 않았다면, 다음 Job의 요청시간으로 now(현재시간)을 셋팅하여

다음 루프에서 힙에 처리 가능 작업을 넣어줄수 있게 만든다.

 

수행가능한 Job들이 힙안에 있다면, 

이미 실행시간이 짧은 순서로 정렬되어있으니, 

total 시간을 더해준다 (수행시간 + 요청으로부터 현재까지의 대기시간)

diskIndex와 별개로 finished를 이용해 작업진행 갯수를 Count하여 루프를 빠져나온다.

(while문으로 이미 올라가버린 상태에 diskIndex와 같이 쓰는 경우,  남은 Job들을 count해주지 못하고 끝날수 있다)

 

 

 

과거에도 이 문제가 참 어려웠었는데,

다시 푸는 지금도 여전히 어렵다.