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

문제

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

코드

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

struct cmp{
    bool operator()(vector<int> a,vector<int> b){        
        return a[1]>b[1];
    }
};
bool compare(vector<int> a,vector<int> b){
    if(a[0]==b[0]) return a[1]<b[1];
    return a[0]<b[0];
}
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int time=0;
    int size=jobs.size();
    int cnt=0;
    
    sort(jobs.begin(),jobs.end(),compare);
    vector<int> visit(size,0);
    
    priority_queue<vector<int>,vector<vector<int>>,cmp> pq;
    
    
    for(int i=0;i<size;i++){
        if(visit[i]==1) continue;
        pq.push(jobs[i]);
        visit[i]=1;
        time=jobs[i][0];
        while(!pq.empty()){
           
            time+=pq.top()[1];
            answer+=time-pq.top()[0];
            pq.pop();

            for(int i=0;i<size;i++){
                if(visit[i]==1) continue;
                if(jobs[i][0]<time){
                    pq.push(jobs[i]);
                    visit[i]=1;
                }
                else break;
            }
        }
    }
    
    
    answer/=size;
    return answer;
}

풀이

핵심은 현재시간보다 작은 요청시간의 값이 있을 때 그 중에서 작업시간의 값이 작은 순서대로 일처리를 해주면 됩니다.

코드를 보시면 jobs가 정렬되어 있다는 보장이 없기 때문에 먼저 요청시간 오름차순으로 정렬을 해줍니다.

sort(jobs.begin(),jobs.end(),compare);

jobs를 순서대로 돌면서 아직 방문하지 않았으면 현재 시간을 기준으로 요청시간이 작은 작업을 우선순위큐에 넣으면서 작업을 해주는건데 사실 설명하기가 좀 어렵습니다.