디스크 컨트롤러(문제51)

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<Job> q = new PriorityQueue<>((o1,o2)->o1.requestTime - o2.requestTime);
        int idx = 0;
        for(int[] job : jobs){
            q.add(new Job(idx++, job[0], job[1]));
        }
        // q.sort((o1,o2)->o1.requestTime - o2.requestTime); 오버라이딩 되나봄
        PriorityQueue<Job> waitQ = new PriorityQueue<>();
        Job first = q.poll();
        
        int time=first.requestTime;
        waitQ.add(first);
        int totalReturnTime=0;
        while(!(q.isEmpty() && waitQ.isEmpty())){
            
            while(!q.isEmpty() && q.peek().requestTime <= time){
                waitQ.add(q.poll());
            }
            
            if(!waitQ.isEmpty()){
                Job complete = waitQ.poll();
                time += complete.durationTime;
                totalReturnTime += time - complete.requestTime;
            }
            //여기왔는데도 대기큐가 비었다? 시간이 문제
            else{
                // BUG 2 FIX: 다음 작업이 도착할 시간으로 현재 시간을 점프시킴
                // 이 로직이 없으면 NullPointerException이 발생하거나 무한 루프에 빠질 수 있음
                if (!q.isEmpty()) {
                    time = q.peek().requestTime;
                }
            }
        }
        
        return totalReturnTime/jobs.length;
    }
    
    class Job implements Comparable<Job>{
        int durationTime;
        int requestTime;        
        int taskId;
        
        Job(int taskId, int requestTime, int durationTime){
            this.taskId = taskId;
            this.requestTime = requestTime;
            this.durationTime = durationTime;
        }
        
        @Override
        public int compareTo(Job other){
            if(this.durationTime == other.durationTime){
                if(this.requestTime == other.requestTime){
                    return this.taskId - other.taskId;
                }else{
                    return this.requestTime - other.requestTime; 
                }
            }else{
                return this.durationTime - other.durationTime;
            }
        }
    }
}

개선 버전

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<Job> q = new PriorityQueue<>((o1,o2)->o1.requestTime - o2.requestTime);
        int idx = 0;
        for(int[] job : jobs){
            q.add(new Job(idx++, job[0], job[1]));
        }
        // q.sort((o1,o2)->o1.requestTime - o2.requestTime); 오버라이딩 되나봄
        PriorityQueue<Job> waitQ = new PriorityQueue<>();
        Job first = q.poll();
        
        int time=first.requestTime;
        waitQ.add(first);
        int totalReturnTime=0;
        while(!(q.isEmpty() && waitQ.isEmpty())){
            
            while(!q.isEmpty() && q.peek().requestTime <= time){
                waitQ.add(q.poll());
            }
            
            if(waitQ.isEmpty()){
                if (!q.isEmpty()) {
                    time = q.peek().requestTime;
                    continue;
                }
            }
        
            Job complete = waitQ.poll();
            time += complete.durationTime;
            totalReturnTime += time - complete.requestTime;
        }
        return totalReturnTime/jobs.length;
    }
    
    class Job implements Comparable<Job>{
        int durationTime;
        int requestTime;        
        int taskId;
        
        Job(int taskId, int requestTime, int durationTime){
            this.taskId = taskId;
            this.requestTime = requestTime;
            this.durationTime = durationTime;
        }
        
        @Override
        public int compareTo(Job other){
            if(this.durationTime == other.durationTime){
                if(this.requestTime == other.requestTime){
                    return this.taskId - other.taskId;
                }else{
                    return this.requestTime - other.requestTime; 
                }
            }else{
                return this.durationTime - other.durationTime;
            }
        }
    }
}

답지

import java.util.*;

public class Solution {
    private static class Job {
        public final int start;
        public final int duration;

        private Job(int start, int duration) {
            this.start = start;
            this.duration = duration;
        }
    }

    public int solution(int[][] rawJobs) {
        Job[] jobs = new Job[rawJobs.length];
        for (int i = 0; i < jobs.length; i++) {
            jobs[i] = new Job(rawJobs[i][0], rawJobs[i][1]);
        }
        Arrays.sort(jobs, Comparator.comparingInt(job -> job.start));

        Queue<Job> q = new LinkedList<>(Arrays.asList(jobs));
        PriorityQueue<Job> pq = new PriorityQueue<>(
                Comparator.comparingInt(job -> job.duration));

        int exec = 0;
        int time = 0;
        while (!q.isEmpty() || !pq.isEmpty()) {
            while (!q.isEmpty() && q.peek().start <= time) {
                pq.add(q.poll());
            }

            if (pq.isEmpty()) {
                time = q.peek().start;
                continue;
            }

            Job job = pq.poll();
            exec += time + job.duration - job.start;
            time += job.duration;
        }

        return exec / jobs.length;
    }
}