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

디스크 컨트롤러

문제 링크

디스크 컨트롤러

분석

하드디스크는 한번에 한 작업만 수행할 수 있습니다.

우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다.

1. 작업 요청에 대한 번호, 요청 시각, 소요 시간을 저장해 두는 대기 큐가 존재합니다.
   • 처음에 이 큐는 비어있습니다.
2. 하드디스크가 작업을 하고있지 않고 대기 큐가 비어있지 않다면 우선 순위가 가장 높은 작업을 꺼내 하드디스크에 작업을 시킵니다.
   • 작업의 소요시간이 짧은 것, 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
3. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
4. 하드디스크가 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내 하드디스크에 작업을 시킵니다.
   • 이 과정에서 걸리는 시간은 없다고 가정합니다.
5. 작업이 끝나마자마자 또 다른 작업을 시작할 수 있습니다.

우선순위 디스크 컨트롤러가 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 반환해야합니다.

jobs[i]는 i번 작업에 대한 정보며, [s, l] 형태로 2차원 배열입니다. s는 작업이 요청되는 시점입니다.
l은 작업의 소요시간입니다.

풀이

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    
    // 작업들을 요청 시간 기준으로 오름차순 정렬한다.
    sort(jobs.begin(), jobs.end());
    
    // 우선순위 큐(최소 힙)를 사용하여 소요 시간이 가장 짧은 작업을 먼저 처리한다.
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    int currentTime = 0;    // 현재 시간
    int index = 0;          // 아직 큐에 넣지 않은 작업의 인덱스
    int totalWait = 0;      // 전체 대기 시간 누적
    int count = 0;          // 처리된 작업 수
    
    // 모든 작업이 처리될 때까지 반복한다.
    while (count < jobs.size())
    {
        // 현재 시간까지 요청된 작업을 우선순위 큐에 넣는다.
        while(index < jobs.size() && jobs[index][0] <= currentTime)
        {
            // 소요 시간 기준으로 정렬하기 위해서 소요 시간, 요청 시간 순서로 삽입한다.
            pq.push({jobs[index][1], jobs[index][0]});
            ++index;
        }
        
        if (!pq.empty())
        {
            // 큐에서 가장 소요 시간이 짧은 작업을 꺼낸다.
            auto [duration, requestTime] = pq.top();
            pq.pop();
            
            // 현재 시간 갱신
            currentTime += duration;
            // 대기 시간은 작업 종료 시점 - 요청 시점이다.
            totalWait += currentTime - requestTime;
            // 처리한 작업 수를 증가시킨다.
            ++count;
        }
        else
        {
            // 대기 중인 작업이 없을 경우 다음 작업의 요청 시간으로 현재 시간을 이동한다.
            currentTime = jobs[index][0];
        }
    }
    
    // 평균 대기 시간을 계산
    answer = totalWait / jobs.size();
    
    return answer;
}

작업을 우선순위 기준으로 오름차순으로 정렬합니다.

작업을 우선순위대로 순서대로 처리하기 위해 우선순위 큐를 사용합니다.

다음 과정을 반복하게 됩니다.

1. 요청 시점이 현재 시간 이하인 작업을 우선순위 큐에 추가합니다.
2. 우선순위 큐에서 소요 시간이 가장 짧은 작업을 꺼내 처리합니다.
3. 작업이 없을 경우, 다음 요청 시점으로 시간을 이동합니다.

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 정렬 $O(n \ log \ n)$
• 모든 작업이 처리될 때까지 반복하는 반복문 $O(n)$
• 현재 시간까지 요청된 작업을 우선순위 큐에 넣는 반복문 $O(n)$
  • 큐의 삽입 $O(log \ k)$
    • k는 큐에 들어간 작업 수입니다.
    • 삽입은 기본적으로 $O(log \ k)$이지만, n번 일어납니다.
• 큐의 삭제 $O(n \times log \ n)$
  • 삭제는 기본적으로 $O(log \ n)$이지만, n번 일어납니다.
• $O(n \ log \ n) + O(n) + O(n) \times O(log \ k) + O(n \ log \ n)$

공간 복잡도는 $O(n)$입니다.

• 우선순위 큐 $O(n)$

테스트 성능

테스트 1 〉 통과 (0.10ms, 4.21MB)
테스트 2 〉 통과 (0.08ms, 4.48MB)
테스트 3 〉 통과 (0.08ms, 4.17MB)
테스트 4 〉 통과 (0.07ms, 4.21MB)
테스트 5 〉 통과 (0.09ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 3.71MB)
테스트 7 〉 통과 (0.08ms, 4.21MB)
테스트 8 〉 통과 (0.05ms, 4.15MB)
테스트 9 〉 통과 (0.03ms, 4.21MB)
테스트 10 〉 통과 (0.10ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.22MB)
테스트 12 〉 통과 (0.01ms, 4.13MB)
테스트 13 〉 통과 (0.01ms, 4.14MB)
테스트 14 〉 통과 (0.01ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 4.28MB)
테스트 16 〉 통과 (0.01ms, 3.68MB)
테스트 17 〉 통과 (0.01ms, 4.2MB)
테스트 18 〉 통과 (0.01ms, 3.68MB)
테스트 19 〉 통과 (0.01ms, 4.19MB)
테스트 20 〉 통과 (0.01ms, 4.13MB)