[프로그래머스] Level 3. 디스크 컨트롤러

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

프로그래머스

 

해결 방법

1. job구조체를 만들어 리스트에 넣은 뒤, 요청순서대로 정렬한다.
2. 현재까지 들어온 요청작업을 넣기위해 pq를 만들고, 문제에서 제시한 작업우선순위 조건을 compare함수에 구현한다.
3. 현재시간 minute과, 배열의 어디까지 pq에 넣었는지를 검사하는 index를 놓는다.
4. 현재 시간보다 askTs가 먼저라면 pq에 모두 넣어준다. 하나씩 꺼내서 작업처리를해준다.

 

주의할 점이 몇가지 있다.

 

1. pq의 우선순위를 결정하는 compare함수에서,  processTs 가 적은게 앞에와야한다. 하지만 pq는 기본적으로 최대힙이기 때문에, true가 리턴될 경우, 우선순위가 낮다고 판단되기 때문에 부호를 반대로 설정해야 한다.

 

bool compare(Job& a, Job& b){
    if(a.processTs != b.processTs) return a.processTs > b.processTs;
    if(a.askTs != b.askTs ) return a.askTs > b.askTs;
    return a.id > b.id;
}

 

 

2. 현재까지 요청된 모든 작업이 끝나서pq가 비어있더라도, 뒤에 작업이 남을 수 있다. 예를들면 현재까지 pq 에 있는 작업을 모두 종료했을때 10초이고, 그 다음작업 요청이 15초에 들어왔을 경우, minute을 15초로 옮기고 다시 pq에 넣어주어야한다. 

//큐는 비어있지만, 작업이 남아있고 askTs 가 현재 minute보다 뒤에있을경우. 
if(pq.empty() && minute < jobs[index].askTs){ minute = jobs[index].askTs;}

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

using namespace std;

struct Job{
    int id =0;
    int askTs = 0;
    int processTs =0;    
};

bool compare(Job& a, Job& b){
    if(a.processTs != b.processTs) return a.processTs > b.processTs;
    if(a.askTs != b.askTs ) return a.askTs > b.askTs;
    return a.id > b.id;
}

int solution(vector<vector<int>> _jobs) {
    int answer = 0;
    
    //jobs 세팅하기
    vector<Job> jobs;
    for(int i=0; i< _jobs.size(); i++){jobs.push_back({i,_jobs[i][0],_jobs[i][1]});}
    sort(jobs.begin(), jobs.end(), [](Job& a , Job& b){return a.askTs < b.askTs;}); //요청순으로 정렬
    
    priority_queue<Job,vector<Job>, bool (*)(Job&,Job&)> pq(compare);
    
    int index = 0;
    int minute = 0;
    while(index < jobs.size() || !pq.empty()){
        
        if(index < jobs.size()){
            if(pq.empty() && minute < jobs[index].askTs){ minute = jobs[index].askTs;}
            
            while(index <jobs.size() && jobs[index].askTs <= minute){
                pq.push(jobs[index]);
                index++;
            }
        }
        
        Job current = pq.top();
        pq.pop();
        minute += current.processTs; //종료시간 맞추기.
        answer += minute - current.askTs; //총 걸린 시간 더하기
        
    }
    return answer / jobs.size();
}