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

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

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

 

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

struct Job{
    int request, time;
    Job(int request, int time)
        : request(request), time(time)
    {}
};

struct compare{
    bool operator()(Job a, Job b){
        return a.time>b.time;
    }
};

bool cmp(vector<int> a, vector<int> b){
    return a[0]<b[0];
}


int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int now=0;
    int i=0;
    sort(jobs.begin(), jobs.end(), cmp);        //요청시간 오름차순으로
    priority_queue<Job, vector<Job>, compare> pq;
    while (i<jobs.size() || !pq.empty()){
        if (i<jobs.size() && now>=jobs[i][0]){   //현재 시간 기준 대기열에 있을 작업을 모두 넣기
            pq.push({jobs[i][0], jobs[i][1]});
            i++;
            continue;
        }
        if (!pq.empty()){       //작업시간 짧은 것부터 꺼냄
            int r=pq.top().request;
            int t=pq.top().time;
            pq.pop();
            answer+=((now-r)+t);
            now+=t;
        }
        else{               //대기열 없는 경우 뒤에거 시간으로 맞춰놓기
            now=jobs[i][0];
        }
    }
    return answer/jobs.size();
}

처음엔 큐를 2개 써서 하나는 요청시간 오름차순으로 정렬, 하나는 소요시간 오름차순 정렬.. 했더니 안됐다. 먼저 시간이 빠른 애부터 뽑은 후, 현재 시간 기준으로 가능한 애들(대기중인 애들)을 모두 뽑은 후 소요시간 오름차순 큐에 넣는다.. 일단 "현 대기열 중 소요시간이 제일 적은 작업을 뽑는다" 는 아이디어는 생각해 냈으나.. 구현 도중 뭔가 중간 로직에 오류가 있는듯 해서.. 한참 헤매다 답을 보고 풀었다.. ㅜㅜ

 

아이디어는 비슷하다. 요청시간을 오름차순으로 sort 한 뒤, 하나씩 큐에 넣는다(이때 큐는 우선순위 큐로, 소요시간이 가장 적은 애가 앞에 나오는 Min Heap 이다). 큐에 넣는 조건은 "요청 시간<=현재 시간"이다. 즉 현재 시간 기준으로, 대기열에 있을 애들이다. 

큐에 무언가 있으면, 제일 top에 있는 애를 뽑고 answer과 현재 시간을 바꾸어 준다.

큐에 없으면, 대기열에 아무것도 없다는 뜻이므로 현재 시간을 지금 작업 요청 시간으로 당겨준 후 다시 위의 과정을 반복한다.