문제

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

풀이

우선순위 큐를 활용하여 문제를 풀었음. (정렬이 필요하므로)

정렬

1. 작업큐
   1. 작업큐의 경우 기본적으로 작업이 들어온 순서대로 정렬되어야 한다. 또한, 같은 시간에 작업이 들어온 경우, 작업 시간이 더 짧은 작업을 먼저 처리하는것이 효율적이다.
2. 대기큐
   1. 작업 시간이 짧은 순서대로 정렬해주자.

작업 고르기

1. 현재 대기중인 작업이 있는 경우
   1. 대기 큐에서 작업시간이 가장 짧은 작업을 고른다.
   2. 만약 현재 시간보다 작업 큐에서 꺼낸 작업의 시작시간이 더 크다면, 시간을 꺼낸 작업의 시작시간으로 변경해준다. (새로운 작업은 현재 시간보다 100초 이후에 시작될수도 있다.)
2. 현재 대기중인 작업이 없는 경우
   1. 요청이 들어온 순서대로 작업을 고른다.

작업 실행

작업 시간만큼 반복하면서 시간을 더해주고, 현재 시간에 새로운 작업이 추가되면 작업큐에서 대기큐로 옮겨준다.

작업 완료

작업이 완료되었다면 걸린 시간을 정답에 추가해준다. 작업큐와 대기큐가 모두 비었다면, 전체 작업의 갯수만큼 나눠서 리턴해준다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    static int[] current;
    static int time;
        public int solution(int[][] jobs) {
        int answer = 0;
        int count = jobs.length;
        PriorityQueue<int[]> list = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1]-o2[1];
                }
                else return o1[0]-o2[0];
            }
        });
               PriorityQueue<int[]> wait = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        for (int i = 0; i < jobs.length; i++) {
            list.add(jobs[i]);
        }

        while (true) {
            if (wait.isEmpty() && list.isEmpty()) break;
            // 맨 위에 있는거 꺼내기
            if (wait.isEmpty()) {
                current = list.poll();
                if (current[0] > time) {
                    time = current[0];
                }
            } else {
                current = wait.poll();
            }

            for (int i = 0; i < current[1]; i++) {
                if (!list.isEmpty() && list.peek()[0] <= time) {
                    wait.add(list.poll());
                }
                time++;
            }
            answer += time - current[0];
        }

 
        return answer / count;
    }

}

한국어 읽는게 제일 어렵다..