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

프로그래머스

 

• 해당 요청시점에서 들어온 작업 중 소요 시간이 짧은 작업들부터 처리하는 것이 관건
• 작업 배열을 요청 시점 기준으로 오름차순 정렬하고 이후 우선순위 큐에 소요 시간 기준으로 오름차순 정렬
• 이후 모든 작업을 완료할 때까지 작업 수행

 

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

using namespace std;

// 소요 시간이 짧은 것부터 처리하는 것이 평균을 줄이는 방법
// 일단 jobs 배열을 오름차순으로 정렬하고 우선순위 큐에 소요 시간을 기준으로 오름차순 정렬하면 될듯

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

int solution(vector<vector<int>> jobs) {
    // 각각 총 소요시간, 현재까지의 소요시간, 작업 카운트
    int totalCost = 0, curCost = 0, cnt = 0;
    
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    
    // 정렬
    sort(jobs.begin(), jobs.end()); 
    
    // 작업이 끝나지 않은 동안
    while(cnt < jobs.size() || !pq.empty()) {
        
        // 요청 시간이 현재까지의 소요 시간보다 작으면
        if(cnt < jobs.size() && jobs[cnt][0] <= curCost) {
            pq.push(jobs[cnt]); 
            cnt++;
            continue;
        }
        
        // 우선순위 큐에 수행할 작업이 들어있다면
        if(!pq.empty()) {
            curCost += pq.top()[1];
            totalCost += curCost - pq.top()[0];
            pq.pop();
        }
        // 작업은 남았는데 현재 시간에 우선순위 큐에 들어있는 작업이 없다면
        else {
            curCost = jobs[cnt][0];
        }
    }
    
    return totalCost / jobs.size();
}