프로그래머스 - 디스크 컨트롤러 - Level 3

문제

풀이전략

1. priority_queue를 내가 원하는 우선순위에 따라 바꿔주어야한다. 따라서 몰랐던 방법인 priority_queue<vector, vector<vector>, cmp> pq; 이 방법을 확실하게 익히자. 이는 오름차순 정렬이다.

코드

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

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

int solution(vector<vector<int>> jobs){
    int answer = 0, j = 0, time = 0;
    // 이렇게 할 경우 요청이 빠른 순으로 정렬 된다.
    sort(jobs.begin(), jobs.end());
    // 내가 원하는 방향대로 priority_queue를 sort할 수 있도록 하는 방법이다.
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    while(j < jobs.size() || !pq.empty()){
        // 새로운 일을 넣을 수 있는 시간이 되었을 때
        if(jobs.size() > j && time >= jobs[j][0]){
            pq.push(jobs[j++]);
            continue;
        }
        if(!pq.empty()){
            // priority_queue에 제일 앞에 위치한 친구를 빼는 과정 즉 소요시간이 적은 순으로 배열, 그 값의 top을 time에 더해준다. 
            time += pq.top()[1];
            // answer에 현재시간 - 들어간 시간을 넣어준다. 이것이 즉 소요시간이다.
            answer += time - pq.top()[0];
            pq.pop();
        }
        // 큐가 비어있고, 시간이 아직 다음 job에 도달하지 않았을 경우 도달하기 위해 jobs[j][0]으로 시간을 바꿔준다. 
        else time = jobs[j][0];
    }
    return answer/jobs.size();
}

소감

Priority_Queue를 내가 원하는 방법에 따라 정렬하는 방법을 몰랐다. 이번에 확실하게 알았으니 잘 복습하도록 해야겠다.