[C++] 프로그래머스 디스크 컨트롤러

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

프로그래머스

풀이

예시에서 확인할 수 있듯이, 현재 가능한 작업 중 처리 시간이 짧은 것을 먼저 처리 하면 전체 평균 시간을 줄일 수 있다.

1. 먼저, 작업을 시작 순서 기준 오름차순으로 정렬한다.

2. 우선순위 큐는 처리 시간 기준, 최소 힙이 되도록 선언한다. 

3. 현재 시간을 저장하기 위한 변수 curr_t 와 작업을 우선순위 큐에 넣기 위한 idx를 선언한다.

4. 모든 작업을 우선순위 큐에 넣었거나, 모든 작업을 끝낼 때 까지 while문을 반복한다.

   4.1 현재 시간보다, 요청 시간이 작은 작업(현재 처리 가능한 작업)을 모두 우선순위 큐에 넣는다.

   4.2 수행할 작업이 있는 경우,

          4.2.1 answer에 요청 시점부터 종료까지 시간을 더한다. 이때, p.pt는 수행 시간, curr_t-p.st 는 대기 시간이다.

          4.2.2 현재 시간을 업데이트 하고 pop한다. curr_t <- curr_t + p.pt

   4.3 수행할 작업이 없는 경우,

          4.3.1 처리할 작업이 남았는데 현재 시각이 처리할 작업의 시작 시간보다 작은 경우, 현재 시각을 다음 작업이 들어오는 시각으로 변경한다(무한 루프 방지).

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

using namespace std;

struct Info{
    int st, pt;
    Info(vector<int> a){
        st=a[0];
        pt=a[1];
    }
    bool operator<(const Info& b) const {
        return pt > b.pt;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    sort(jobs.begin(), jobs.end());
    priority_queue<Info> pq;
    // 현재 시간 선언
    int curr_t=jobs[0][0];
    // 현재 인덱스 선언
    int idx=0;
    while (idx < jobs.size() || !pq.empty()){
        // 작업이 남아 있으면서 현재 시간에 수행할 수 있는 작업이라면,
        // 모두 우선순위 큐 push
        if (idx<jobs.size() && jobs[idx][0] <= curr_t){
            pq.push(Info(jobs[idx++]));
            continue;
        }
        // 현재 시간에 수행할 수 있는 작업을 전부 넣었다면,
        // 소요 시간이 가장 작은 것부터 작업 처리 수행
        if (!pq.empty()){
            Info p = pq.top();
            answer+= p.pt + curr_t - p.st;
            curr_t += p.pt;
            pq.pop();
        }
        else {
            // 수행할 작업이 없는 경우 다음 작업으로 바로 넘어가기
            curr_t = jobs[idx][0];
        }
        
    }
    
    answer /= jobs.size();
    return answer;
}