문제

개발자 준모는 운영체제를 만들었습니다. 준모가 만든 운영체제는 프로그램의 우선순위와 호출된 시각에 따라 실행 순서를 결정합니다. 모든 프로그램에는 1부터 10까지의 점수가 매겨져 있으며, 이 점수가 낮을수록 우선순위가 높은 프로그램입니다. 각 프로그램들은 실행 시간이 정해져 있으며 프로그램이 호출되면 대기상태에 있다가 자신의 순서가 되면 실행 시간 동안 실행된 뒤 종료됩니다.

준모가 만든 운영체제는 호출된 프로그램들 중 우선순위가 가장 높은 프로그램을 먼저 실행합니다. 호출된 각 프로그램은 자신보다 우선순위가 높은 호출된 프로그램이 모두 종료된 후에 실행됩니다. 단, 실행 중인 프로그램보다 우선순위가 높은 프로그램이 호출되어도 실행 중이던 프로그램은 중단되지 않고 종료될 때까지 계속 실행됩니다. 또한, 우선순위가 같은 프로그램들 중에서는 먼저 호출된 프로그램이 먼저 실행됩니다.

다음은 1번부터 4번까지의 4개의 프로그램이 호출된 예시입니다.

예를 들어, 1번부터 4번까지 4개의 프로그램의 점수가 순서대로 2, 1, 3, 3이며, 호출된 시각은 0, 5, 5, 12초이고, 수행시간은 10, 5, 3, 2라고 가정해 봅시다.

1번 프로그램이 0초에 호출될 때 실행 중인 프로그램이 없으므로, 0초에 1번 프로그램이 바로 실행됩니다. 1번 프로그램은 10초에 종료되며, 2, 3번 프로그램이 새로 호출됐습니다.
호출된 2, 3번 프로그램 중 2번 프로그램의 점수가 1로 우선순위가 높습니다. 2번 프로그램은 5초에 호출되어 10초에 실행될 때까지 5초 동안 대기했습니다. 2번 프로그램은 15초에 종료되며, 4번 프로그램이 새로 호출됐습니다.
호출된 3, 4번 프로그램은 점수가 같지만, 3번 프로그램이 먼저 호출되었기 때문에 3번 프로그램이 먼저 실행됩니다. 3번 프로그램은 5초에 호출되어 15초에 실행될 때까지 10초 동안 대기했습니다. 3번 프로그램은 18초에 종료됩니다.
4번 프로그램이 마지막으로 실행되며, 4번 프로그램은 12초에 호출되어 18초에 실행될 때까지 6초 동안 대기했습니다. 4번 프로그램은 20초에 종료됩니다.
모든 프로그램이 종료되는 시각은 20초이며, 각 프로그램이 대기한 시간은 순서대로 0, 5, 10, 6초입니다. 점수가 1인 프로그램의 대기시간 합은 5고, 점수가 3인 프로그램의 대기시간 합은 16 임을 알 수 있습니다.

프로그램들의 정보를 나타내는 2차원 정수 배열 program이 주어질 때, 모든 프로그램들이 종료되는 시각과 프로그램의 점수마다 대기시간의 합을 정수 배열에 담아 return 하는 solution 함수를 완성하세요. return 해야 하는 answer 배열은 길이가 11인 정수 배열입니다. answer[0]은 모든 프로그램들이 종료되는 시각을 의미하며, answer[i](1 ≤ i ≤ 10)는 프로그램의 점수가 i인 프로그램들의 대기시간의 합을 의미합니다.

제한 사항

1 ≤ program의 길이 ≤ 100,000
program[i]은 i+1번 프로그램의 정보를 의미하며, [a, b, c]의 형태로 주어집니다.

• a는 프로그램의 점수를 의미하며, 1 ≤ a ≤ 10 을 만족합니다.
• b는 프로그램이 호출된 시각을 의미하며, 0 ≤ b ≤ 10,000,000을 만족합니다.
• c는 프로그램의 실행 시간을 의미하며, 1 ≤ c ≤ 1,000을 만족합니다.
• a, b쌍이 중복되는 프로그램은 입력으로 주어지지 않습니다. 즉, 호출된 시각이 같으면서 점수도 같은 프로그램은 없습니다.

입력

program : [[2, 0, 10], [1, 5, 5], [3, 5, 3], [3, 12, 2]]

출력

[20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0]

내가 했던 풀이 방법

1. answer을 11 크기의 0으로 채워진 배열로 초기화한다.
2. program을 호출 시간을 기준으로 정렬한다. 만약, 호출 시간이 같다면 우선순위가 높은 프로그램을 우선으로 정렬한다.
3. time을 0으로 초기화한 뒤, 더 이상 프로그램이 없거나 운영체제에 실행할 프로그램이 없을 때까지 아래 내용들을 반복한다.
4. 현재 time을 포함하여 이전에 호출된 프로그램들을 우선순위 큐(운영체제)에 넣어준다. 이때, 운영체제는 minHeap이며, 호출된 시간이 같을 경우엔 우선순위를 기준으로 정렬한다.
5. 만약 아직 호출되지 않은 program이 존재하지만, 운영체제에는 program이 존재하지 않을 때 time을 가장 먼저 호출될 program의 호출 시간으로 변경하고 해당 program을 운영체제에 넣어준다.
6. 운영체제에서 가장 먼저 실행될 프로그램을 dequeue로 반환하고 현재 시간에서 호출 시간을 뺀 값을 해당 우선순위의 대기 시간에 더해준 다음 time을 해당 프로그램의 실행 시간을 더해준다. 즉, answer[i]에는 대기 시간이 더해지게 될 것이고, 현재 시간은 해당 프로그램이 끝난 시점으로 바뀌게 될 것이다.
7. 4~6을 반복한 다음 time의 값을 answer[0]에 저장해준다.

코드

function solution(program) {
    var answer = Array(11).fill(0);
    program.sort((a, b) => a[1] - b[1] || a[0] - b[0]);

    class MinHeap {
        constructor() {
            this.heap = [null];
        }

        enqueue(value) {
            this.heap.push(value);
            let current = this.heap.length - 1;
            let parent = Math.floor(current / 2);

            while (
                parent > 0 &&
                (this.heap[current][0] < this.heap[parent][0] ||
                    (this.heap[current][0] === this.heap[parent][0] && this.heap[current][1] < this.heap[parent][1]))
            ) {
                [this.heap[current], this.heap[parent]] = [this.heap[parent], this.heap[current]];
                current = parent;
                parent = Math.floor(current / 2);
            }
        }

        dequeue() {
            if (this.heap.length === 1) return null;
            if (this.heap.length === 2) return this.heap.pop();

            let result = this.heap[1];
            this.heap[1] = this.heap.pop();
            let current = 1;

            while (true) {
                let left = 2 * current;
                let right = left + 1;
                let smallest = current;

                if (
                    left < this.heap.length &&
                    (this.heap[left][0] < this.heap[smallest][0] ||
                        (this.heap[left][0] === this.heap[smallest][0] && this.heap[left][1] < this.heap[smallest][1]))
                ) {
                    smallest = left;
                }
                if (
                    right < this.heap.length &&
                    (this.heap[right][0] < this.heap[smallest][0] ||
                        (this.heap[right][0] === this.heap[smallest][0] && this.heap[right][1] < this.heap[smallest][1]))
                ) {
                    smallest = right;
                }

                if (smallest === current) break;
                [this.heap[current], this.heap[smallest]] = [this.heap[smallest], this.heap[current]];
                current = smallest;
            }
            return result;
        }

        getSize() {
            return this.heap.length - 1;
        }
    }

    let os = new MinHeap();
    let time = 0;

    while (program.length > 0 || os.getSize() > 0) {
        while (program.length > 0 && program[0][1] <= time) {
            os.enqueue(program.shift());
        }

        if (program.length > 0 && os.getSize() === 0) {
            time = program[0][1];
            os.enqueue(program.shift());
        }

        let temp = os.dequeue();
        if (temp) {
            answer[temp[0]] += time - temp[1];
            time += temp[2];
        }
    }

    answer[0] = time;
    return answer;
}

회고

우선순위 큐를 단순히 minHeap으로만 구현해서 삽질을 좀 했던 문제... 우선순위 큐만이 문제가 아니긴 했지만 다소 복잡해서 문제 이해가 오래걸리긴 했는데 침착하게 오래 잡았으면 풀 수 있었을 것 같기도 하다. 중간에 enqueue할 때 shift가 아니라 index 같은 걸로 했다면 시간을 조금 더 절약할 수 있을 것 같긴했는데 불안불안하긴 했지만 통과했다. 휴~