1. 문제에 대하여 📦

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

(1) 조건 분석 📊

Job의 요소로는, 작업의 번호, 작업의 요청 시각, 작업의 소요 시간이 있다.
Job은 매 초마다, 대기큐에 적재된다.
대기큐는 다음과 같은 약속으로 내부 우선순위가 정해진다.
- 소요 시간이 짧을수록 우선순위가 높다.
- 소요 시간이 같다면 요청 시각이 빠를수록 우선순위가 높다.
- 소요시간, 요청시각이 같다면, 작업 번호가 작을수록 우선순위가 높다.
디스크는 하나의 일을 그것의 소요시간만큼 해낸다.

이때, 임의의 작업이 그것의 요청시각부터 끝날때까지 걸린 시간을 a라고 했을 때, 모든 작업의 a의 평균을 구하라.

2. 코드가 나오기까지 🛠️

KEY WORD: 우선순위 큐, 시뮬레이션

문제에서 제시한 조건을 구현하면 된다.
필자는 이를 위해 우선순위 큐를 사용했다. Job의 경우 객체 구현이 쉬웠지만, 문제는 디스크의 움직임을 어떻게 표현할 것인가에 대한 것이였다. 필자는 이 또한 클래스 객체로 만들어 구현했다.

(1) 시간복잡도 분석 ⏳

처음 문제 풀이를 시간초과 맞았는데, 이유는 시간단위로 문제를 풀었기 때문이다. 이는 불필요한 연산 횟수를 증가시켜서 시간 초과를 낸다.

Job의 길이가 500, 요청 시점은 최대 1,000초, 소요시간 또한 1,000초인데, 만약에 500개의 요청이 모두 1,000초부터 시작하고, 소요 시간도 1,000초라고 가정해보자. 그러면 1,000 초 이후부터 500개의 요청을 1,000초마다 하나씩 처리해야 한다. 이는 $1,000 + 500 \times 1,000 = 501,000$ 의 연산 횟수가 든다.

내부 계산이 더 있으므로, 이는 시간 초과를 낼 확률이 많다.

하지만 이벤트 기반으로 문제를 푼다면, 외부 반복문은 $500$번만 반복하면 된다. 이것이 가능한 이유는

일마다 소요 시간이 있기 때문에 1초씩 반복문 돌리지 말고, 그 일이 끝나는 시점으로 이동 가능.
일이 끝나는 시점보다 시작 시점이 빠른 일들은 한 번에 큐에 집어 넣어도 계산이 틀리지 않음

때문이다.

3. 코드 🌐

(1) SUDO CODE 💬

0. JOB에 대한 우선순위 큐 만들기 
1. 일을 처리하는 디스크 객체 만들기. (현재 작업 중인 일의 번호, 총 일 수행 시간, 끝낸 일 수, 현재 맡은 일이 끝나는 시간) 을 담고 있어야 한다.
2. 디스크가 끝낸 일 수가 모든 일의 개수가 될 때까지 다음 반복문을 수행한다.
    1. 현재 디스크가 맡은 일이 끝나는 시점보다 일 시작 시점이 빠른 Job을 큐에 넣기
    2. 디스크가 일 중이면 넘어가기
    3. 디스크가 일 중이지미 않으면, 큐에서 하나 꺼내서 작업, 디스크 객체 업데이트

(2) JAVA CODE ☕

import java.util.*;

class Solution {

    static class Job {
        int i; // 번호
        int t; // 요청 시각
        int w; // 소요 시간

        public Job (int i, int t, int w){
            this.i = i;
            this.t = t;
            this.w = w;
        }

        @Override
        public String toString(){
            return "일 번호: " + i + " 요청 시각:" + t + " 소요 시간:" + w; 
        }
    }

    static class Disk {
        int iter; // 작업 도는 지시자
        int amount_work_time; // 일 수행 시간 총량
        int done_cnt; // 끝낸 일 수
        int end; // 현재 맡은 일이 끝나는 시간

        public Disk () {
            this.iter = 0;
            this.amount_work_time = 0;
            this.done_cnt = 0;
            this.end = 0;
        }

    }

    public int solution(int[][] jobs) {

        PriorityQueue<Job> pq = new PriorityQueue<>((j1, j2)-> {
            if(j1.t == j2.t && j1.w == j2.w) return j1.i - j2.i;
            if(j1.w == j2.w) return j1.t - j2.t;
            return j1.w - j2.w; });

        Arrays.sort(jobs, (a,b) -> a[0] - b[0]);   
        Disk disk = new Disk();

        while(disk.done_cnt < jobs.length){

            while(disk.iter < jobs.length && disk.end >= jobs[disk.iter][0]) {
                pq.add(new Job(disk.iter, jobs[disk.iter][0], jobs[disk.iter][1]));
                disk.iter++;
            }

            if(pq.isEmpty()){ // 0ms 때의 작업이 없다.
                if(disk.iter < jobs.length) disk.end = jobs[disk.iter][0];
            }else {
                Job now = pq.poll();
                disk.amount_work_time += disk.end + now.w - now.t;
                disk.end += now.w;
                disk.done_cnt++;
                System.out.println(disk.end + now.w - now.t);
            }

        }

        return disk.amount_work_time/jobs.length;
    }
}