문제

Programmers, 디스크 컨트롤러

핵심

• 입력의 크기가 작아 구현에 초점을 맞춘다.
• 한 번에 하나의 작업만을 처리할 수 있는 디스크에서 각 작업의 요청부터 종료까지 걸린 시간을 가장 줄이는 방법을 구하는 문제이다. 각 작업 큐에는 작업 요청 시점과 작업 소요 시간이 주어진다. 한 작업이 걸리는 시간은 작업 소요 시간 + 대기 시간이며, 대기 시간은 현재 시각에서 요청 시간을 차감하여 구할 수 있다.
• 각 작업이 요청부터 종료까지 걸린 시간이 최소화되려면 가장 빨리 끝나는 작업부터 처리해야 한다. 여기서 주의해야 할 점은 요청되지 않은 작업은 처리하지 않아야 한다는 것이다. 즉, 요청 시간이 충족된 작업에만 가장 짧은 소요 시간의 작업을 선택한다. 우선순위 큐를 이용해 매 순간 가장 빨리 끝나는 작업을 효율적으로 찾을 수 있다.

개선

// 요청 시간이 충족된 작업이 없다면
if (pq.empty()) 
	++time;

• 해당 코드에서는 요청되지 않은(요청 시간이 충족되지 않은) 작업에 대해서 시간을 1씩 증가시킨다. 문제에서 작업의 소요 시간 범위가 1000이라 크게 문제 되지 않았지만, 소요 시간 범위가 크다면 비효율적인 코드가 된다. 이를 해결하기 위해선 해당 시점에 가장 짧은 요청 시간의 작업을 기억해 두고 time 효과적으로 증가시킬 수 있게 한다.

코드

시간복잡도

• $O(N^2)$

C++

#include <string>
#include <vector>
#include <queue>
#include <tuple>
#include <iostream>
using namespace std;

int solution(vector<vector<int>> jobs) {
    auto comp = [](auto& a, auto& b) {
        return a.second > b.second;
    };
    // pq -> 요청시간, 소요시간 [최소 힙 - 소요시간]
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq(comp);
    for (int i = 0; i < jobs.size(); ++i)
        pq.push({jobs[i][0], jobs[i][1]});
    queue<pair<int, int>> q;
    int time = 0;
    int ans = 0;
    while (!pq.empty()) {
        auto [req, elapse] = pq.top();  
        tie(req, elapse) = pq.top();
        int minReq = req;
        while (!pq.empty() && req > time) {
            pq.pop();
            q.push({req, elapse});
            if (!pq.empty()) {
                tie(req, elapse) = pq.top();
                if (minReq > req)
                    minReq = req;
            }
        }
        if (pq.empty()) { // 요청시간이 충족된 작업이 없음
            time += minReq - time;
        } else {          // 요청시간이 충족된 작업이라면 
            pq.pop();
            ans += (elapse + time - req);
            time += elapse;
        }
        while (!q.empty()) {
            pq.push(q.front());
            q.pop();
        }
    }
    return ans / jobs.size();
}

Java

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int i = 0; i < jobs.length; ++i) 
            pq.add(new int[]{jobs[i][0], jobs[i][1]});
        Queue<int[]> q = new LinkedList<>();
        int time = 0;
        int ans = 0;
        while (!pq.isEmpty()) {
            int[] top = pq.peek();
            int req = top[0];
            int elapse = top[1];
            int minReq = req;
            while (!pq.isEmpty() && req > time) {
                pq.poll();
                q.add(new int[]{req, elapse});
                if (!pq.isEmpty()) {
                    top = pq.peek();
                    req = top[0];
                    elapse = top[1];
                    if (minReq > req)
                        minReq = req;
                }
            }
            if (pq.isEmpty()) {
                time += minReq - time;
            } else {
                pq.poll();
                ans += (elapse + time - req);
                time += elapse;
            }
            while (!q.isEmpty())
                pq.add(q.poll());
        }
        return ans / jobs.length;
    }
}