[프로그래머스/Java] 디스크 컨트롤(heap 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 heap 파트 문제 중 하나인 '디스크 컨트롤'을 Java를 사용해서 풀어보았다. 

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

프로그래머스

 

 

 자바에서는 heap 자체를 제공하지는 않지만, 기능이 같은 PriorityQueue를 제공한다. 따라서 PriorityQueue를 이용해서 heap을 구현해 줬다. 

 우선 일 정보를 담을 Job 클래스를 선언해줬다. 이때 Comparable을 implement 해줬는데, 그 이유는 CompareTo 메서드를 override 하면 추후 Job을 담을 Priority Queue에서의 우선순위를 미리 설정해 줄 수 있기 때문이다. 문제에서 요구한 우선순위에 맞게 priority를 구성하기 위해서 Comparable을 implement 해줬다. 그래서 CompareTo를 override 한 것을 보면, 우선적으로 run_time을 고려하고, run_time이 같다면 req_time을, req_time도 같다면 id를 오름차순으로 고려하는 것을 볼 수 있다.

 Job 클래스를 다 구성했으면, main 함수로 넘어가서 우선 jobs 배열을 요청 시간에 따라 정렬해준다. job 배열을 정렬할 때는, 2차원 배열이므로 Comparator를 이용하여 어떤 기준으로 정렬할 건지를 명시해줘야 한다. 요청시간에 따라 정렬한 이유는, 요청 시간이 빠를수록 대기 heap에 더 빨리 진입해야 하기 때문이다.

 다음으로 while문으로 반복하면서 답을 계산해준다. 우선 heap에 요청 시점이 다가온 job들을 넣어준다. 넣어준 후 heap이 비어있다면, 시점이 다가온 job이 없다는 뜻이므로, 시간을 첫 번째 요소의 요청시점까지 시간을 skip 해준다. (첫 번째 요소의 요청시점이 가장 가깝다. 정렬해 뒀기 때문이다.) 만약, heap이 비어있지 않다면, 대기 heap의 peek의 위치에 있는 job, 즉 우선순위가 가장 높은 job을 꺼내서 실행해 준다. 여기서 실행해 준다는 것은, 시간을 해당 job의 실행 시간만큼 skip 해주고, answer에 반환시간을 더해주는 것이다.

 마지막으로 반환시간의 평균을 구해야하므로, answer에 일의 개수를 나눠주면서 리턴하면 마무리된다. 

import java.util.*;

class Job implements Comparable<Job> {
    int id;
    int req_time; //요청시점
    int run_time; //작업시간
    
    public Job(int id, int req_time, int run_time) {
        this.id = id;
        this.req_time = req_time;
        this.run_time = run_time;
    }
    
    // heap에서의 우선순위 결정
    @Override
    public int compareTo(Job other) {
        if (this.run_time == other.run_time) {
            if (this.req_time == other.req_time) {
                return (this.id - other.id);
            } else return (this.req_time - other.req_time);
        } else return (this.run_time - other.run_time);
    }
}

class Solution {
    public int solution(int[][] jobs) {
        //요청시간 기준 오름차순으로 정렬
        Arrays.sort(jobs, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        
        int answer = 0;
        PriorityQueue<Job> waiting = new PriorityQueue<Job>();
        int len = jobs.length;
        int i = 0; //jobs 배열 idx
        int time = 0; //현재시간
        while (i < len || !waiting.isEmpty()) {
            //대기heap에 요청시간이 온 job 넣기
            while (i < len && jobs[i][0] <= time) {
                waiting.add(new Job(i, jobs[i][0], jobs[i][1]));
                i++;
            }
            
            //우선순위가 가장 높은 job 실행하기
            if (!waiting.isEmpty()) {
                Job j = waiting.poll();
                time += j.run_time;
                answer += (time - j.req_time);
            } else time = jobs[i][0];
        }
        
        return answer / len;
    }
}