[프로그래머스 LV3] - 디스크 컨트롤러(minheap) c++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42627#

프로그래머스

접근방법

jobs를 요청시간에 맞춰 정렬.

 

정렬된 jobs를 바탕으로,

하나씩 minheap에 넣을 건데,

이 때, time을 계산해야 한다.

 

time이 jobs[idx][0]보다 작고 min_heap이 비어있는 경우,

이 때는 요청이 존재하지 않는 시간을 뜻한다.

 

그렇기 때문에, time = jobs[idx][0]으로

time 값을 변경해준다.

 

변경해주었다면, 이제 jobs[idx]를 minheap에 넣어주면 된다.

작업의 요청시간이 time보다 작다면 계속 넣는다.

 

minheap에는 지금 time의 값보다 요청 시간이 작은 친구들만 모여있을 것이다.

하나 씩 뽑아서, time을 조정하고,

answer = time - pair[0]으로, 평균 대기 시간을 계산해준다.

 

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

struct Comparator{
    bool operator()(const vector<int>& a, const vector<int>& b) {
        return a[1] > b[1];
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue<vector<int>, vector<vector<int>>, Comparator> pq;
    sort(jobs.begin(), jobs.end());
    int idx = 0;
    int time = 0;
    while(idx < jobs.size() || !pq.empty()) {
        if (idx < jobs.size() && time >= jobs[idx][0]) {
            pq.push(jobs[idx++]);
            continue;
        }
        if (!pq.empty()) {
            vector<int> pair = pq.top();
            pq.pop();
            time += pair[1]; // 처리 시간 추가
            answer += time - pair[0]; //answer 업데이트
        }
        else {
            time = jobs[idx][0];
        }
    }
    return answer / jobs.size();
}

개선할 점

jobs를 요청시간에 맞춰 정렬 하는 것에 주목.

 

priority_queue Comparator 커스터마이징 가능.

 

Comparator는 class가 될 수도 있고, 함수가 될 수도 있고, struct가 될 수도 있음.