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

문제 링크

 

풀이

1) 지금 처리되고 있는 작업이 끝나는 시간(현재 시간)을 초과하지 않으면 2) 요청된 작업들은 우선 순위 큐에 담아 작업 시간이 빠른 순서대로 처리합니다. 3) 그렇지 않은 작업은 요청 시간이 도래할 때까지 기다렸다가 1번, 2번을 반복합니다. 우선 순위 큐에 비교 함수를 넣을 때 함수 객체를 넣어도 되고 람다 표현식을 넣어도 됩니다.

내부적으로 생성자를 호출하는데 람다식은 생성자가 없기 때문에 직접 초기화해줘야 합니다. 템플릿으로 넣어주는 것은 타입이기 때문입니다.

 

코드

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

int solution(vector<vector<int>> jobs) 
{
    int answer = 0, current_time = 0;
    int job_idx = 0;
    auto cmp = [](vector<int> a, vector<int> b) { return a[1] > b[1]; };

    sort(begin(jobs), end(jobs));
    priority_queue < vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
    while (job_idx < jobs.size() || !pq.empty())
    {
        if (job_idx < jobs.size() && jobs[job_idx][0] <= current_time)
        {
            pq.push(jobs[job_idx++]);
            continue;
        }
        else if (!pq.empty())
        {
            // 지금 시간에 작업 시간을 더한다
            current_time += pq.top()[1];

            // 작업이 완료된 시간에서 요청 시간을 빼주면 소요시간
            auto required = current_time - pq.top()[0];
            answer += required;
            pq.pop();
        }
        // 요청 시간이 현재 시간보다 늦다면
        // 현재 시간을 요청 시간으로 갱신
        else
            current_time = jobs[job_idx][0]; 
    }
    return answer / jobs.size();
}