[promgrammers] 디스크 컨트롤러

문제 링크입니다

🚀 [디스크 컨트롤러] Lv. 3 문제

힙을 사용해 문제를 해결 하였습니다.

힙은 c++ < queue > 에 포함되어 있는 priority_queue 를 사용하여구현하였습니다.

이 문제는 요청 시간이 작업중에 겹치는 일이 발생하면 작업 시간이 짧은 작업부터 처리하여 풀어야합니다.

먼저 작업 요청 순서를 기준으로 작업을 하기 위해 작업들을 요청이 들어오는 시간을 기준으로 정렬하였습니다.
우선순위 큐는 작업 시간이 짧은 것부터 처리하기위해 오름차순으로 비교인자를 설정하였다.
이후 작업 시간에 작업이 없으면 작업을 추가하여 우선수위 큐에 저장하고, 그 외로 작업이 있으면(우선순위 큐가 비어있으면) 작업시간에 다음 가장짧은 작업의 작업시간을 더해주어 수정하고, 총 진행 시간을 작업 시간에서 작업 요청 시간을 빼주어 계산하여줍니다.
마지막으로 총 진행 시간에서 작업의 개수를 나누어주어 평균을 계산하여 문제를 해결합니다.

💎 전체 코드는 다음과 같습니다.

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

struct compare{
    bool operator()(vector<int> a, vector<int> b){
        return a[1] > b[1];
    }
};
int solution(vector<vector<int>> jobs) {
    priority_queue<vector<int>, vector<vector<int> >, compare > pq;
    int work_time=0;
    int task_count=0;
    int total_time = 0;
    sort(jobs.begin(), jobs.end());

    while(task_count < jobs.size() || !pq.empty()){
        // 작업 시간 보다 작업이 없으면 작업 추가
        if(task_count < jobs.size() && jobs[task_count][0] <= work_time){
            pq.push(jobs[task_count++]);
            continue;
        }
        // 작업이 있으면
        if(!pq.empty()){
            work_time += pq.top()[1];
            total_time += work_time- pq.top()[0];
            pq.pop();
        }
        // 작업이 없으면
        else{
            work_time = jobs[task_count][0];
        }
    }
    return total_time/jobs.size();
}