프로그래머스(힙; 디스크 컨트롤러) c++

// FCFS처럼 보이지만 SJF로 돌아감 (비선점)
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<vector<int>> jobs) {
    // jobs[i] = {요청시간, 작업시간}
    sort(jobs.begin(), jobs.end());     // 도착시간 순 정렬   
    
    // {작업시간, 요청시간} 순으로 넣어야 작업시간 기준으로 힙이 됨(스케줄러)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    int idx = 0;
    int currentTime = 0;
    int totalTime = 0;
    int n = jobs.size();
    
    // 인덱스가 작업 개수보다 적거나 스케줄러가 아직 있다면 실행
    while (idx < n || !pq.empty())
    {
        // 인덱스가 작업 개수보다 작고 현재 시간에서 도착한 요청시간을 스케줄러에 추가
        // currentTime이 0이기 첫번째 작업의 요청시간이 0 초과일 경우 동작 하지 않음
        // jobs[idx][0] = 요청시간
        while(idx < n && jobs[idx][0] <= currentTime)
        {
            // {작업시간, 요청시간} -> 스케줄러에 추가
            pq.push({jobs[idx][1], jobs[idx][0]});
            idx++;
        }
        
        // 작업을 시작 못하거나 작업을 끝내고도 이후 스케줄러에 작업이 안들어 왔을 수도 있기에 해당 조건을 넣어줘야함
        // 요청시간 순으로 정렬한 jobs[idx][0](요청시간)을 currentTime = 요청시간으로 점프함
        if(pq.empty())
        {
            currentTime = jobs[idx][0];
            continue;                   // while 명령문이기에 다시 위로 올라감
        }
        
        // pq.top()은 실행시간 기준으로 정려되었기에 workTime이 가장 짧은것이 앞으로 오고 대입함 이후 pop으로 작업을 처리했음.
        auto [workTime, requestTime] = pq.top();
        pq.pop();
        
        // 현재시간 += 실행시간
        currentTime += workTime;
        totalTime += currentTime - requestTime;     // (완료시간 - 요청시간) 누적
    }
    
    // 반환시간 = 종료시간 - 요청시간
    // 평균 반환시간 = (반환시간 / 작업 수)
    return totalTime / n;
}

 

해설:

평균 반환시간을 구해야 하며 요청시간도 존재하므로 작업이 안들어올 수 있는 상황을 고려하여 로직을 구성해야 됨.