[1일 1알고] 디스크 컨트롤러

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

프로그래머스

디스크 컨트롤러는 우선순위를 사용하는 문제입니다.

 

이런 문제는 어떻게 풀지는 머리속에 생각이 나지만 막상 구현을 하려니까 헷갈리는 문제가있네요

// 한 번에 하나의 작업만 수행 가능한 하드디스크 
// 우선순위 디스크 컨트롤러를 사용함
// [번호, 시각, 소요시간]
// 1.소요시간(짧은것) 2.요청시각(빠른것) 3.작업번호(작은것) 순으로 우선순위가 높음
// 작업 중간에 스위칭 되지는 않음
// 작업을 마치는 시간과 새로운 작업이 추가되는 시점이 같다면 작업 추가를 먼저하고 고르게 됨

위의 조건을 지켜야합니다.

 

그렇다면 우선순위를 지키기 위해 기본적으로 priority queue를 사용해야겠네요

 

pq는 말그대로 queue의 성질을 띄기 때문에 맨 처음 원소만을 얻을 수 있다는 것입니다.

그런데 소요시간이 요청시각보다 우선순위가 높지만

시간이 도달하지 않았는데 pq에서 빼내서 실행할 수는 없습니다.

 

결론적으로 시간과 우선순위를 동시에 고려해야하는 것입니다.

 

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

struct Work
{
    int spendTime;
    int startTime;
    int num;
};

// jobs = [s, l] s=요청시각, l=소요시간
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    const int N = jobs.size();

    sort(jobs.begin(), jobs.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0])
            return a[1] < b[1];

        return a[0] < b[0];
    });

auto cmp = [](const Work& a, const Work& b) {
    if (a.spendTime == b.spendTime)
    {
        if (a.startTime == b.startTime)
        {
            return a.num > b.num;
        }
        return a.startTime > b.startTime;
    }
    return a.spendTime > b.spendTime;
};

    priority_queue < Work, vector<Work>, decltype(cmp)> pq(cmp);

    int jobidx = 0;
    int jobsfinished = 0;
    int time = 0;
    int result = 0; // 반환시간 계산
    while (jobsfinished < N)
    {
        while (jobidx < N && jobs[jobidx][0] <= time)
        {
            pq.push({ jobs[jobidx][1], jobs[jobidx][0], jobidx });
            ++jobidx;
        }

        if (pq.empty())
        {
            time = jobs[jobidx][0];
            continue;
        }

        
        auto[spendTime, startTime, num] = pq.top();
        if (startTime <= time)
        {
            pq.pop();
            ++jobsfinished;
            time += spendTime;

            result += time - startTime;
        }
        else
        {
            ++time;
        }
    }
    answer = result / N;
    return answer;
}

 결론적으로 만들어진 코드입니다.

 

일단 그렇게 주어질것이라고 생각은 들지만 기본적으로 jobs가 요청시간에 따라 정렬되어 주어진다는 말이 없어 이에 따라 정렬했습니다.

 

추가적으로 sort에서 사용하는 조건과 priority queue에서 사용하는 comparator의 조건은 반대입니다.

sort는 true인 경우 앞으로 보내지만,

pq는 true인 경우 우선순위가 낮다고 봐 뒤로 보냅니다.