Programmers 디스크 컨트롤러 C++

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

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

 

level 3 , Heap 에 해당하는 문제입니다.

학부 수업시간 때, FIFO 부터 시작해서 OS 컨트롤러를 공부할 때 접해봤던 비슷한 문제입니다.

 

평균시간을 줄이기 위해 접근한 방법은

대기큐에 있는 작업 중에서! 가장 수행시간이 짧은 것 부터 처리하는 것! 으로 접근해봤습니다.

 

좀더 자세한 설명은 코드와 함께 주석으로 설명하였습니다.

 

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

typedef pair<int, int> pii;

int solution(vector<vector<int>> v) {
    int answer = 0;
    int time = 0;

    // 우선 큐에 대기 중인 프로세스 중에서 소요시간이 가장 짧은 것들을 우선적으로 처리하도록 접근
    // => 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
    // 힙의 조건은 시간을 우선적으로 처리하되, 시간이 동일하면 사용시간이 짧은 녀석을 먼저 가져온다

    priority_queue<pii, vector<pii>, greater<pii> > q;

    // 내 나름 사용하기 편하게 변경
    vector<pii> jobs;
    for (int i = 0; i < v.size(); i++)
        jobs.push_back({ v[i][0], v[i][1] });
    
    // jobs의 값이 작업요청 순서대로 들어왔다는 말이 없으므로 정렬부터 함
    sort(jobs.begin(), jobs.end());

    // 먼저 들어온 작업부터 처리
    time = jobs[0].first + jobs[0].second;
    answer = jobs[0].second;
    
    int finish_task = 1;
    int task = 1;
    
    while(finish_task < jobs.size()){
        // 현재 time 까지 요청이 들어온 작업들을 큐에 넣고 작업
        for(int i = task; i < jobs.size(); i++){
            if(jobs[i].first <= time){
                // greater 로 꺼낼때 작업시간이 짧은 순으로 꺼내기 위해 swap 해서 푸쉬
                q.push({jobs[i].second, jobs[i].first});
                task++;
           }
            // time 보다 후에 들어온 작업은 우선처리 조건에 포함되지 않음
            else break;
        }
        
        // 현재 대기큐에 작업이 없다 -> 다음 작업을 가져옴 task        
        if(q.empty()){
            time = jobs[task].first+jobs[task].second;
            answer += jobs[task++].second;
            finish_task++;
        }
        // 현재 대기큐에 작업이 있다
        else{
            pii now_task = q.top();
            q.pop();
            finish_task++;
            answer += (time - now_task.second) + now_task.first;
            time += now_task.first;
        }
    }

    return answer/jobs.size();
}