[프로그래머스/Level3] 디스크 컨트롤러

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42627

문제 접근

우선 배열을 Job클래스의 리스트로 변경하여 진행했다.
우선순위 큐는 처리 시간으로 정렬하게 했다.

여기서 핵심은 다음과 같다고 생각한다.

1. 현재 처리 중인 요청이 끝나는 시간까지 들어올 요청만을 큐에 넣는다.
2. 큐가 비었을 경우 제일 앞에 있는 요청을 넣어주는 것인데 아래 그림과 같이 동시에 온 요청을 처리해주어야한다.
   
   2-1. A가 처리된 이후, 큐는 비어있을 것이다. 제일 앞에 온 요청은 B와 C인데 이때는 C가 시간이 덜 걸리니까 C가 먼저 처리되어야한다.(이것 때문에 실패한 케이스가 있었다...)

소스 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public class Job {
        public Job(int comeTime, int elapseTime) {
            this.comeTime = comeTime;
            this.elapseTime = elapseTime;
        }
        
        public int comeTime;
        public int elapseTime;
    }
    
    public int solution(int[][] jobs) {
        int answer = 0;
        int curTime = 0;
        int finishTime = 0;
        
        List<Job> jobList = Arrays.stream(jobs)
            .map(job -> new Job(job[0], job[1]))
            .sorted((job1, job2) -> job1.comeTime - job2.comeTime) //도착한 시간으로 정렬
            .collect(Collectors.toList());
        PriorityQueue<Job> pq = new PriorityQueue<>((job1, job2) -> job1.elapseTime - job2.elapseTime); //걸리는 시간이 작은 것부터 꺼내도록 함
        List<Integer> servingTime = new ArrayList<>(); //처리까지 걸린 시간을 저장할 리스트
        
        while (!jobList.isEmpty() || !pq.isEmpty()) {
            Job curJob;
            //대기 중인 요청이 없는 경우
            if (pq.isEmpty()) {
                curJob = jobList.get(0); //리스트에 제일 앞에 있는 요청을 꺼내옴
                //제일 앞에 있는 요청과 동시에 온 요청이 있는지 확인
                //동시에 있는 요청이 있는 경우, 우선순위 큐에 넣어서 제일 짧은 시간이 걸리는 애가 먼저 처리하도록 함
                int curJobComeTime = curJob.comeTime;
                List<Job> concurrentJobs = jobList.stream()
                    .filter(job -> job.comeTime == curJobComeTime)
                    .collect(Collectors.toList());
                concurrentJobs.forEach(job -> {
                    pq.add(job);
                    jobList.remove(job);
                });
                
                curTime = curJob.comeTime;
            }
            
            curJob = pq.poll();
            //현재 처리할 요청이 끝나는 시간을 계산
            finishTime = curTime + curJob.elapseTime;
            //리스트에서 현재 요청이 끝나는 시간 안에 도착할 요청들을 우선순위 큐에 넣음
            while (!jobList.isEmpty()) {
                Job job = jobList.get(0);
                if (job.comeTime > finishTime) {
                    break;
                }
                
                pq.add(job);
                jobList.remove(0);
            }
            
            //요청 도착부터 처리 끝날 때까지 걸린 시간 계산
            servingTime.add(finishTime - curJob.comeTime);
            curTime = finishTime;
        }
        
        //평균 계산 및 소수점 자리 버림
        return (int) Math.floor(
            servingTime.stream()
                    .mapToInt(i -> i)
                    .average()
                    .getAsDouble()
        );
    }
}