[프로그래머스 lv3] 디스크 컨트롤러 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

평균 시간을 최소화 하기 위해서는 현재 시간 t 이전에 들어온 작업 중 가장 소요시간이 작은 작업을 선택해야 한다.

 

우선순위 큐에 (소요시간, 요청시간)을 넣어놓으면  소요시간이 가장 작은 순으로 원소를 pop 할 수 있다.

이때, 현재 시간 t보다 요청 시간이 작거나 같은 작업만 선택할 수 있으므로 처음으로 요청시간이 t보다 작거나 같은 작업을 찾는다.

해당 작업을 찾았을 때 처리시간(현재시간 t - 요청 시간 + 소요시간)을 총합에 기록해둔 뒤 작업 크기로 나누어 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii =tuple<int, int, int>;

#define X first
#define Y second

int solution(vector<vector<int>> jobs) {
    
    priority_queue<ii, vector<ii>, greater<ii>> pq, tmp;
    
    for (auto v : jobs)
        pq.push({v[1], v[0]}); //{소요시간, 요청시간}
    
    int t = 0, sum = 0;
    while (!pq.empty()) {
        
        // 현재 시간 t 이전에 들어온 요청 중 가장 소요시간이 짧은 작업 선택
        int sz = pq.size();
        bool flag = false;
        while (sz--) {
            ii cur = pq.top();
            pq.pop();
            if (cur.Y > t) tmp.push(cur);
            else {
                sum += t-cur.Y+cur.X;
                t += cur.X;
                flag = true;
                break;
            }
        }
        
        while (!tmp.empty()) {
            pq.push(tmp.top());
            tmp.pop();
        }
        
        //t 이전에 요청된 작업이 없다면 t 증가
        if (!flag) t++;
    }
    
    return sum/(int)jobs.size();
}