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

문제 링크

디스크 컨트롤러

풀이

우선순위 큐로 푸는 문제

1. 작업을 수행하지 않을 때는 요청 들어온 것부터 실행해야 하니 jobs를 오름차순 정렬해 요청이 들어온 순서대로 정렬한다.
2. pq는 실행 시간을 오름차순으로 정렬하기 위함으로 커스텀 함수를 써서 선언해준다.
3. pq가 비어있으면 요청 들어온 순서대로 처리를 해야하므로 pq에 푸쉬하고 curTime을 갱신해준다. curTime은 한 작업이 시간을 의미한다. push 해줬으니 다음 작업을 위해 i++를 해준다.
   3-1. pq가 빌 때까지 반복해주는데, 현재 작업이 끝나는 시간에 따라 curTime을 갱신해주고 answer도 갱신해준다.
   3-2. 현재 시간이 뒤의 작업들의 요청이 들어온 시간보다 크다면(한 작업을 할 때 다른 작업들의 요청이 들어온다면) pq에 푸쉬해준다.
   3-3. 탈출문 잘 작성해주고 answer를 리턴한다.

코드

#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) {
    int answer = 0;
    
    sort(jobs.begin(), jobs.end());
    priority_queue<vector<int>, vector<vector<int>>, compare> pq;
    
    int curTime=0;
    int i=0;
    while(1)
    {
        if(i>=jobs.size()) break;
        if(pq.empty()) //pq가 비어있다면 바로 push
        {
            curTime = jobs[i][0];
            pq.push(jobs[i]);
            i++;
        }
        
        while(!pq.empty())
        {
            vector<int> curTask = pq.top();
            pq.pop();
            curTime += curTask[1];
            answer += curTime - curTask[0];
        
            while(1) //현재 시간 기준으로 요청 들어온 작업들 push
            {
                if(i>=jobs.size()) break;
                if(curTime>=jobs[i][0])
                {
                    pq.push(jobs[i]);
                    i++;
                }
                else break;
            }
        }    
        
    }
    
    answer/=jobs.size();
    
    return answer;
}