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

문제

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

프로그래머스

 

문제풀이

작업이 끝나는 최종 시간은 항상 같다. 그리고 최종 시간을 구하는 문제도 아니었다.

작업이 끝난 시간 - 작업을 요청받은 시간을 최소로 만드는 문제이다.

 

작업이 끝났으면 바로바로 작업을 해야 하므로,

작업의 정보가 들어있는 jobs를 요청 시간 기준으로 오름차순으로 정렬한다.

 

그다음 작업의 소요시간이 짧은 것이 top에 오는 우선순위 큐를 만들어준다.

작업을 하게 되면 그다음 작업은 이전에 한 작업의 소요시간만큼 작업 시간이 추가되는 셈이다.

(이해가 잘 안 된다면 문제에서 그림을 보면 이해될 것이다.)

그렇기 때문에 지금 작업을 할 수 있는 것이 여러 개가 있다면 작업시간이 짧은 것을 먼저 해야 한다.

 

    for (idx = 0; idx < jobs.size();) {
        if (jobs[idx][0] <= prev) {
            pq.push(jobs[idx]);
            idx++;
        }

prev라는 변수는 이전 작업이 끝난 시간을 저장하기 위해 선언한 변수이다.

작업 시간이 담긴 jobs를 탐색하면서 prev 이하인 작업을 찾는다. (당장 할 수 있는 작업들)

그다음 우선순위에 넣고 더 있나 idx를 늘려가며 찾는다.

 

        else {
            if (pq.empty()) {
                prev = jobs[idx][0];
            }
            else {
                answer += (prev + pq.top()[1] - pq.top()[0]);
                prev += pq.top()[1];
                pq.pop();
            }
        }

위랑 이어진 코드이다.

만약 우선순위큐가 비어있다면 작업을 할 수 없으므로, 다음 작업의 요청 시간으로 건너뛴다.

비어있지 않다면 우선순위의 top부분의 작업을 하면 된다.

작업을 요청한 시간부터 작업이 끝난 시간을 구해야 하므로

이전 작업이 끝난  prev - 요청시간 (작업을 하지 못하고 대기한 시간) + 작업시간을 더하고 pop 한다.

 

    while (!pq.empty()) {
        answer += (prev + pq.top()[1] - pq.top()[0]);
        prev += pq.top()[1];
        pq.pop();
    }

for문을 통해 모든 작업이 우선순위큐에 담겼지만 작업이 끝나지 못한 경우가 있다.

그 경우에는 우선순위큐가 비워질 때까지 반복하면 된다.

 

코드

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

struct cmp {
    bool operator()(vector<int>a, vector<int>b) {
        return a[1] > b[1];
    }
};

int solution(vector<vector<int>> jobs) {
    int answer(0), idx(0), prev(0);
    sort(jobs.begin(), jobs.end());
    priority_queue<vector<int>, vector<vector<int>>, cmp>pq;

    for (idx = 0; idx < jobs.size();) {
        if (jobs[idx][0] <= prev) {
            pq.push(jobs[idx]);
            idx++;
        }
        else {
            if (pq.empty()) {
                prev = jobs[idx][0];
            }
            else {
                answer += (prev + pq.top()[1] - pq.top()[0]);
                prev += pq.top()[1];
                pq.pop();
            }
        }
    }
    while (!pq.empty()) {
        answer += (prev + pq.top()[1] - pq.top()[0]);
        prev += pq.top()[1];
        pq.pop();
    }

    return answer / jobs.size();
}