[프로그래머스/LV3] [PCCP 모의고사 1] 4번 - 우선순위큐 (Java)

[PCCP 모의고사 #1] 4번 - 운영체제

🙋‍♂️ 들어가며

문제를 읽어보니 총 2단계로 진행하면 되겠다

1단계 -> 가장 실행시간이 빠르고, 실행 시작시간이 같다면 점수가 낮은 것을 첫번쨰로 삽입

2단계 -> pq를 생성후 점수가 낮은, 만약 점수가가 같다면 실행시작시간이 빠를 수록

testcase-1

3순위 -> {3, 6, 4}
2순위 -> {4, 2, 5}
1순위 -> {1, 0, 5}
4순위 -> {5, 0, 5}

위 테스트케이스를 계산하면 이렇게 된다

호출 시각	실행 시작 시각
0	0
2	5
6	10
0	14

testcase-2

1순위 -> {3, 10, 5}
2순위 -> {1, 100, 10}

✅ 정답 코드

import java.util.PriorityQueue;
import java.util.Arrays;


class Solution {
    public long[] solution(int[][] program) {
        long[] answer = new long[11];
        
        // 1. 정렬 (첫번째 값은 무조건 빠른 실행순서)
        Arrays.sort(program, (a,b) -> {
           // 1-1. 시간이 같다면 우선순위 오름차순
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            // 1-2. 원칙적으로는 시간 오름차순
            return Integer.compare(a[1], b[1]);
        });
        
        // 2. pq
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> {
            // 2-1. 만약 우선순위가 같으면 실행시각 시간순
            if(a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            }
            
            // 2-2. 우선시간 순
            return Integer.compare(a[0], b[0]);
        });
        
        long cur_time = 0;
        int idx = 0;
        int N = program.length;
        
        // 3. 검사 (프로그램이 남아있거나 대기열에 프로그램이 있는동안 반복)
        while (idx < N || !pq.isEmpty()) {
            // 3-1. 현재시각까지 호출된 모든 프로그램을 대기열(pq)에 삽입
            while (idx < N && program[idx][1] <= cur_time) {
                pq.offer(program[idx]);
                idx++;
            }
            
            // 3-2. 대기열에 프로그램이 있는 경우 실행
            if (!pq.isEmpty()) {
                int[] cur = pq.poll();
                int cur_score = cur[0];
                int cur_start = cur[1];
                int cur_lasting = cur[2];
                
                // 3-2-a. 대기시간 = (현재시간 - 호출시간)
                answer[cur_score] += (cur_time - cur_start);
                
                // 3-2-b. 현재 작동시간 추가
                cur_time += cur_lasting;
            }
            // 3-3. 대기열은 비었지만 호출될 프로그램이 남은 경우
            else if (pq.isEmpty()) {
                // 3-3-a. 다음으로 가장 빨리 호출될 프로그램으로 점프
                cur_time = program[idx][1];
            }            
        }
        
        // 4. 모든 프로그램이 종료된 시간 저장
        answer[0] = cur_time;
        return answer;
    }
}