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

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

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

풀이

1. 기본 프로세스

 -> 현재 작동중인게 끝나기 전에 들어오는 작업이 있으면 몽땅 queue에다가 다 넣는다

 -> queue는 priority_queue로 조건은 작업시간 짧은게 빨리 나오게!!

     : priority queue는 내림차순으로 뽑고 싶으면 <

     : 오름차순으로 뽑고 싶으면 >이더라 !!!!

 

원래 기존 sort할때 조건은 <가 오름 차순, >가 내림차순이였는데 헷갈림!!

 

-> 다 넣었으면 이제 순서대로 작동 시키기

-> queue가 비었으면 다음 job으로 업뎃!

  -> 요청 들어오는 순으로 미리 sort해놔서 그냥 jobs[i][0]로 하면 됨

 

2. 중간에 일처리 끝내기 전에  미리 total_time에다가 소요시간 다 더해놨으니 job 갯수만큼 나누고 return

 

#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];
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue<vector<int>, vector <vector<int> >, cmp > q;
    sort(jobs.begin(),jobs.end());//요청 빨리오는 순으로 정렬
    
    int i=0;//jobs index용
    int end_time =0;
    int total_time =0;
    
    while(i<jobs.size()||!q.empty())
    {
        //만약 지금 처리중인게 끝나기 전에 도착하는 일 있으면 다 대기순위에 삽입
        if(i<jobs.size() && end_time>=jobs[i][0])
        {
            q.push(jobs[i]);
            i++;
            continue;//1개가 아닐 수도 있다
        }
        
        if(!q.empty())
        {
            //젤 소요시간 짧은게 먼저 나옴
            end_time += q.top()[1];
            total_time+= end_time - q.top()[0]; //최종 완료시간 - 처음 요청시간
            q.pop();
        }
        else//남은 대기순위가 하나도 없다
        {
            end_time = jobs[i][0];//다음 작업 ㄱㄱ
        }
        
    }
    answer = total_time/jobs.size();
    return answer;
}