프로그래머스 42885번
https://school.programmers.co.kr/learn/courses/30/lessons/42627

문제

---

생각하기

---

• 정렬, 우선순위 큐를 사용하는 문제이다.

동작

결과

코드

---

import java.util.*;

class Solution {
    // https://school.programmers.co.kr/learn/courses/30/lessons/42627
    
    public static class Job implements Comparable<Job> {
        int requestTime;
        int requiredTime;
        
        public Job(int requestTime, int requiredTime) {
            this.requestTime = requestTime;
            this.requiredTime = requiredTime;
        }
        
        @Override
        public int compareTo(Job o) {
            return requiredTime - o.requiredTime;
        }
    } // End of Job class
    
    public int solution(int[][] jobs) {        
        PriorityQueue<Job> waitingQue = new PriorityQueue<>(); // 소요시간 순으로 정렬 (대기 큐)
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0])); // 요청시간 순으로 정렬
        int sum = 0;
        int n = jobs.length;
        int ans = 0;
        int nowTime = 0;
        int jobsIdx = 0;
        int count = 0;

        while(count < n) {
            
            // 요청시간이 현재 시간보다 크면 큐에서 대기
            while(jobsIdx < n && jobs[jobsIdx][0] <= nowTime) {
                waitingQue.offer(new Job(jobs[jobsIdx][0], jobs[jobsIdx++][1] ));
            }
            
            if(waitingQue.isEmpty()) {
                // 대기 큐가 비어있다는 뜻은 현재 시간 기준으로 다음 작업사이에 여유 시간이 있다는 걸 의미함.
                // 그래서 현재시간을 다음 작업의 요청시간으로 다시 초기화 함
                nowTime = jobs[jobsIdx][0];
            } else {
                Job temp = waitingQue.poll();
                ans += temp.requiredTime + nowTime - temp.requestTime;
                nowTime += temp.requiredTime;
                count++;
            }
        }
        
        return ans / n;
    } // End of solution()
} // End of Solution class