프로그래머스 - 디스크 컨트롤러(Java, LV3) / Heap

https://programmers.co.kr/learn/courses/30/lessons/42627?language=java

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

풀이

• Job 들에 대해서 시간이 빠른순으로 정렬(같을 경우 짧은 시간 순)
• Job 들을 작업시간이 짧은 순으로 우선순위 큐에 보관한다
• 현재 시간(t) 기준으로 작업수행이 가능한 Job들을 우선순위 큐에 넣고 반복문을 통해서 하나씩 꺼내서 수행한다
• 수행한 뒤 다시 현재 시간을 경과된 작업시간만큼 더해주고 다시 작업수행이 가능한 Job들을 우선순위 큐에 넣는다
• 단, 수행 가능한 Job들이 없을 경우 다음 Job이 수행가능 시간으로 시간을 경과시킨다
• 그리고 Job들을 우선순위 큐에 다 넣었으면 우선순위 큐에서 남은 Job들을 처리한다 
• 전체 시간을 계산한다

import java.util.*;

class Job implements Comparable{
    int start;
    int time;
    public Job(int start, int time){
        this.start =start;
        this.time = time;
    }
    
    @Override
    public int compareTo(Object obj2){
        if(this.start < ((Job)obj2).start) return -1;
        else if(this.start == ((Job)obj2).start){
            return (this.time - ((Job)obj2).time);
        }
        else return 1;
    }
}

class Solution {
    public int solution(int[][] jobs) {
        int t = 0;
        int sum = 0;
            
        // 초기화
        Job[] jobArr = new Job[jobs.length];
        for(int i=0; i<jobs.length;i++){
            jobArr[i] = new Job(jobs[i][0], jobs[i][1]);
        }
        
        // heap
        Arrays.sort(jobArr);
        PriorityQueue<Job> q = new PriorityQueue<Job>(new Comparator<Job>(){
            @Override
            public int compare(Job job1, Job job2){
                    return job1.time - job2.time;
            } 
        });
            
        // 하나씩 처리
        int idx = 0; 
        q.add(jobArr[idx++]);
        while(true){
            // 탈출 조건
            if(idx >= jobs.length)
                break;
            
            // 꺼내와서 시간 체크
            Job now = q.poll();
            t = Math.max(t, now.start); 
            t += now.time;
            sum += (t-now.start);
            
            // 시간 되고 범위 안넘을때까지 반복
            for(;idx<jobs.length;idx++){
                if(jobArr[idx].start > t)
                    break;
                else
                    q.add(jobArr[idx]);
            }
            
            // 작업 중단일 경우
            if(q.isEmpty()){
                t = jobArr[idx].start;
            }
            
            // 시간 되고 범위 안넘을때까지 반복
            for(;idx<jobs.length;idx++){
                if(jobArr[idx].start > t)
                    break;
                else
                    q.add(jobArr[idx]);
            }
        }
        
        // 남은 작업 처리
        while(!q.isEmpty()){
            // 꺼내와서 시간 체크
            Job now = q.poll();
            t = Math.max(t, now.start); 
            t += now.time;
            sum += (t-now.start);
        }
        
        int answer = sum/jobs.length;
        return answer;
    }
}