디스크 컨트롤러 (프로그래머스)

평균 시간이 가장 최소가 되기 위해서는 각 작업 소요시간 순으로 처리하면 된다. 여기에는 요청이 먼저 들어온 순서도 고려를 해줘야 한다. 

 

여기서 가장 중요한 부분은 이것이다. 이것을 놓치면 계속해서 실패가 나올 것이다.

• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

현재 작업 시간에 들어온 작업 요청이 없다면 먼저 요청이 들어오는 작업의 시간대로 점프해야 한다. 이 공백 부분을 놓치면 이 문제는 항상 다른 결과를 반환할 것이다.

 

알고리즘 풀이 과정은 다음과 같다.

 

• 요청 받은 작업들을 요청 시간을 기준으로 오름차순 정렬한다.  

• 소요시간을 기준으로 하는 최소 힙을 만든다. 

• 현재 작업 시간 0부터 시작한다.

• 작업 요청 시간이 현재 작업 시간 내에 있다면 그 작업을 최소 힙에 넣는다.

• 만약 없다면, 그 시점으로 부터 먼저 요청이 들어오는 작업으로 현재 작업 시간을 점프한다.

• 힙이 빌때까지 힙에서 작업을 꺼내어 처리하고 요청부터 종료까지의 시간을 기록한다.

• 기록한 시간을 작업의 개수로 나누어 평균을 구한다.

 

코드는 다음과 같다.

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

// 소요시간을 기준으로 최소힙을 만들기 위한 조건
struct cmp
{
    bool operator()(const vector<int>& a, const vector<int>& b)
    {
        return a[1] > b[1];
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    // 요청이 들어온 순으로 정렬한다.
    sort(jobs.begin(), jobs.end());
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    int idx = 0, stack = 0;
    while(true)
    {
        // 처리할 작업이 없는 경우 반복문을 빠져나온다.
        if(idx >= jobs.size() && pq.empty()) break;
        // 처리할 작업이 있는 경우 먼저 요청이 들어온 작업부터 처리
        if(idx < jobs.size() && jobs[idx][0] <= stack)
        {
            pq.push(jobs[idx++]);
            continue;
        }
        if(!pq.empty())
        {
            // 소요 시간 순으로 작업을 처리한다.
            // 소요 시간을 기록해 놓는다.
            stack += pq.top()[1];
            answer += stack - pq.top()[0];
            pq.pop();
        }
        else
            // 처리할 작업이 있는데도 불구하고 요청이 없는경우 요청이 들어오는 시점으로 점프한다. 
            stack = jobs[idx][0]; 
    }
    
    // 평균 소요 시간을 반환한다.
    return answer / jobs.size();
}