[프로그래머스 42627] 디스크 컨트롤러

• 출처: 프로그래머스 42627
• 분류: 힙 · Lv.3

문제

각 작업의 [요청 시각, 소요 시간]이 주어진다. 한 번에 하나의 작업만 수행할 수 있을 때, 요청부터 종료까지 걸린 시간의 평균을 최소화하여 그 정수 부분을 반환한다.

핵심

SJF(Shortest Job First) 스케줄링이다. 현재 시점에 도착한 작업들 중 소요 시간이 가장 짧은 것을 먼저 처리하면 평균 반환 시간이 최소가 된다.

플로우차트

정렬: 요청 시각 순
  │
  ▼
도착한 작업 → 힙에 push
  │
  ├─ 힙 비어있나?
  │    ├─ Yes → time = 다음 작업 도착 시각 → (위로 반복)
  │    └─ No  → 가장 짧은 작업 pop → 실행
  │               │
  │               ├─ 남은 작업 있나?
  │               │    ├─ Yes → (위로 반복)
  │               │    └─ No  → total / N 반환

풀이

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> jobs) {
    sort(jobs.begin(), jobs.end());

    // {소요 시간, 요청 시각} — 소요 시간 기준 최소 힙
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    int n = jobs.size(), time = 0, total = 0, i = 0;

    while (i < n || !pq.empty()) {
        while (i < n && jobs[i][0] <= time) {
            pq.push({jobs[i][1], jobs[i][0]});
            i++;
        }

        if (pq.empty()) {
            time = jobs[i][0];
        } else {
            auto [dur, req] = pq.top();
            pq.pop();
            time += dur;
            total += time - req;
        }
    }

    return total / n;
}

메모

• 힙에 넣을 때 {소요 시간, 요청 시각} 순서로 넣는다. pair의 기본 비교는 first 우선이므로 소요 시간 기준 최소 힙이 된다
• greater<>는 C++14부터 사용 가능한 투명 비교자다. greater<pair<int,int>>와 동일하지만 타입을 반복하지 않아도 된다
• auto [dur, req] = pq.top()은 C++17 구조화 바인딩이다
• 힙이 비어있는데 아직 미처리 작업이 남은 경우는 디스크가 유휴 상태인 것이다. 다음 작업 도착 시각으로 시간을 점프시킨다
• 반환 시간 = 완료 시각 - 요청 시각 = time - req. 이것의 총합을 N으로 나누면 평균이다
• 정렬을 먼저 해야 jobs[i][0] <= time 조건으로 도착 여부를 순차 확인할 수 있다. 정렬하지 않으면 매번 전체를 스캔해야 한다

복잡도

풀이	시간	공간
SJF + 최소 힙	O(N log N)	O(N)