문제

https://school.programmers.co.kr/learn/courses/15008/lessons/121686

풀이

접근방법

...운영체제는 호출된 프로그램들 중 우선순위가 가장 높은 프로그램을 먼저 실행합니다.

-> 힙을 사용하면 되겠네?

힙을 사용하면...

1. 위 그림에서 5초에 2번(우선순위 1)과 3번(우선순위 3) 프로그램을 힙에 넣는다.
2. 10초에 1번 프로그램이 끝날 때, 힙에서 꺼내면 자동으로 우선순위가 낮은 2번이 나온다.

이 아이디어 하나면 풀이에 어려움은 없지만, 구현이 살짝 섞여있는 문제라 복잡할 수 있다. 정답에 맞게 포맷을 만드려면 힙에 값(우선순위)을 넣기 보다는 주어진 배열([우선순위, 호출시간, 실행시간] 그 자체를 넣는게 편하다.

힙 만들기

// [프로그램 점수(우선순위), 호출시각, 실행시간]
// 웨이트 힙은 우선순위 순서로 대기시킵니다.
PriorityQueue<int[]> waitHeap = new PriorityQueue<>((o1, o2) -> {
    if (o1[0] == o2[0]) {
        return o1[1] - o2[1];
    }
    return o1[0] - o2[0];
});

힙에 배열 자체를 요소로 넣기 때문에, 람다식으로 정렬기준을 잡아준다. 우선 배열의 0번 요소인 우선순위로 정렬하고, 우선순위가 같다면 호출시각을 기준으로 정렬해준다.
Arrays.sort 할 때 썼던 람다식 정렬인데, 힙에도 사용이 되다니 정말 편하다.

전체 코드

import java.io.*;
import java.util.*;

class Solution {
    static long[] answer = new long[11];
    
    public long[] solution(int[][] program) {
        // [프로그램 점수(우선순위), 호출시각, 실행시간]
        // 웨이트 힙은 우선순위 순서로 대기시킵니다.
        PriorityQueue<int[]> waitHeap = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        
        // 슬립 힙은 호출시각 순서로 대기시킵니다.
        PriorityQueue<int[]> sleepHeap = new PriorityQueue<>((o1, o2) -> {
            return o1[1] - o2[1];
        });
        
        for (int i = 0; i < program.length; i++) {
            sleepHeap.add(program[i]);
        }
        
        run(waitHeap, sleepHeap);
        
        return answer;
    }
    
    public void run(PriorityQueue<int[]> waitHeap, PriorityQueue<int[]> sleepHeap) {
        long time = -1;
        int run = 0;
        while (true) {
            // 슬립힙과 웨잇힙이 둘 다 비었고, 실행이 0이라면 끝난 것 입니다.
            if (waitHeap.isEmpty() && sleepHeap.isEmpty() && run == 0) {
                break;
            }
            time++;
            // 실행 중 이라면 감소, 즉 0이라면 실행 중 아님.
            if (run > 0) {
                run--;
            }
            
            // 호출
            // 시간이 같다면, 슬립 힙에서 꺼내서 대기열로 넣습니다.
            while (!sleepHeap.isEmpty() && sleepHeap.peek()[1] == time) {
                waitHeap.add(sleepHeap.poll());
            }
            
            // 실행
            if (run == 0 && !waitHeap.isEmpty()) {
                int[] curProgram = waitHeap.poll();
                // 실행시간에 추가합니다.
                run += curProgram[2];
                // 정답에는 실행된 시각 - 대기열에 들어간 시각이 기록됩니다.
                // 주의할 점은 프로그램 별로 저장되는게 아니라 우선순위 별로 기록된다는 것 입니다.
                // ex) 우선순위가 1인 프로그램은 answer[1]에 저장됨.
                answer[curProgram[0]] += time - curProgram[1];
            }
        }
        // 0번에는 프로그램의 총 시간이 들어갑니다.
        answer[0] = time;
    }
}```