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

1. 문제

 

디스크에 작업요청이 들어온다.

 

이때 작업이 들어오는 시간과 수행되는 시간이 주어질 때

 

모든 작업의 요청부터 종료까지의 최소 평균을 구하여라.

 

 

 

 

2. 최소 힙, 그리디 증명

 

이 문제는 그리디한 방법으로 해결할 수 있다.

 

무조건 실행할 수 있는 작업중에서 가장 수행시간이 짧은것을 수행하는 것이다.

 

 

 이것의 증명은 다음과 같이 할 수 있다.

 

만약 수행할 수 있는 작업 a , b, c, d 가 있다고 하자

 

이때 만약 작업시간이 가장 긴 a를 수행하게 되면 시작시간과 상관없이

 

b, c, d 가 기다리는 시간이 a의 긴 수행시간을 더해서 기다려야하기 때문에 전체 평균은 증가할 수 밖에 없는 것이다.

 

반대로 만약 작업시간이 가장 짧은 b를 수행하게 되면

 

나머지들의 대기시간도 짧아지고, 전체 평균은 이것을 선택함으로써 손해는 없다는 것을 알 수 있다.

 

 

따라서 최대힙으로 구현된 우선순위 큐에 음수를 덧붙여서 최소힙으로 원소를 뽑을 수 있게하면

 

문제는 해결된다.

 

 

 

 

3. 코드

여기서 또한 중요한것은 작업들을 시작시간으로 정렬해야한다는 것이다.

벡터간의 비교는 첫 원소부터 수행하므로 그냥 sort하면 시작시간을 기준으로 정렬된다.

 

 

#include <string>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
//: min_heap  
int solution(vector<vector<int>> jobs) {
    int time = 0, sum = 0, i = 0;
    sort(jobs.begin(), jobs.end());
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, 0));
    while(!pq.empty())
    {
        int spend = -pq.top().first, start = pq.top().second;
        pq.pop();
        sum += time - start + spend;
        time += spend;
        while(i < jobs.size() && time >= jobs[i][0])
        {
            pq.push(make_pair(-jobs[i][1], jobs[i][0]));
            i++;
        }
        if(pq.empty() && i < jobs.size())
        {
            time = jobs[i][0];
            pq.push(make_pair(-jobs[i][1], jobs[i][0]));
            i++;
        }
    }
    return sum/jobs.size();
}

 

 

 

 

 

Algorithm/DiskControl.cpp at master · Nor-s/Algorithm (github.com)

programmers.co.kr/learn/courses/30/lessons/42627