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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627#

코딩테스트 연습 - 디스크 컨트롤러

 

 

풀이

문제의 예시에서 평균 시간을 줄이는 법을 설명하였다. 간단히 요약하면

요청 순으로 수행하다가 소요 시간이 더 짧은 것이 들어오면 해당 작업을 다음으로 수행한다.

이 과정에서 우선순위 큐를 이용하면 된다.

 

먼저 요청 순으로 수행하기 위해 jobs 배열을 정렬한다.

다음으로 pair 형태를 가지는 우선순위 큐를 선언한다.

추후에 first를 작업 소요 시간, second를 작업 요청 시간으로 둘 것이다.

 

시간은 0초부터 시작한다. 만약 모든 작업의 요청 시간이 0초보다 크면 어떻게 될까?

수행할 작업이 없으므로 현재 시간을 제일 작은 요청 시간으로 건너뛰면 된다.

 

다음으로, 요청 시간과 현재 시간이 맞는 작업들은 앞서 정의한 우선순위 큐에 삽입해준다.

모두 삽입하였으면 pq에 있는 작업들을 계산하여 현재 시간을 계산하며 총 소요 시간을 answer에 넣는다.

현재 시간은 단순히 작업 시간을 더해주면 되고

총 소요 시간은 요청 시간부터 종료 시간까지를 계산해야 한다.

 

마지막으로 총 소요 시간을 총 작업의 수로 나눠 리턴하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    sort(jobs.begin(), jobs.end());
    //작업을 들어오는 요청 순으로 정렬
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq;
    //first is jobTime, second is reqTime
    
    int i = 0, curTime = 0;
    while(i < jobs.size() || !pq.empty()){
        if(i < jobs.size() && curTime >= jobs[i][0]){
            pq.push(make_pair(jobs[i][1], jobs[i][0]));
            i++;
            continue;
        }
        
        if(!pq.empty()){
            curTime += pq.top().first;
            answer += curTime - pq.top().second;
            pq.pop();
        }
        else {
            curTime = jobs[i][0];
        }
    }
    
    return answer / jobs.size();
}

//jobs[i][0] : i번째 작업의 요청 시각
//jobs[i][1] : i번째 작업의 소요 시간