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

디스크 컨트롤러(Level 3)

문제

전체 문제 보기

코딩테스트 연습 - 디스크 컨트롤러

접근법

이 문제에서 요구하는 바는 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는가?이다. 평균 처리시간을 줄이기 위해서는 작업의 소요시간이 가장 짧은 작업부터 처리하는 SJF(Shortest Jop First) 방식을 사용해야 한다. 그리고 우선순위 큐를 사용하면 현재 대기 중인 작업 중 가장 짧은 작업을 효율적으로 선택할 수 있다.

이 문제를 풀기 위해서 아래와 같이 Job을 정의할 수 있다.

struct Job {
    Job()
        :input(0), processing(0)
    {}
    int input;    // 작업이 요청되는 시점
    int processing;    // 작업의 소요시간
};

그리고 우선순위 큐를 활용한 입력된 작업들의 대기큐를 다음과 같이 정의할 수 있다. waitingQueue에서 소요시간이 짧은 작업이 높은 순위를 가지도록 하여 waitingQueue의 첫 번째 원소가 지금 처리해야 할 작업이 되도록 한다.

// 소요시간이 짧은 작업이 높은 우선순위를 갖도록하는 대기 큐
priority_queue<Job*, vector<Job*>, Compare> waitingQueue;

SJF(Shortest Jop First)방식을 구현하기 위해서 가장 기본적인 방법은 waitingQueue에 현재 시간에 해당하는 작업들을 넣어두고, 첫 번째 작업을 처리한 후 처리한 작업에 소요시간만큼 타이머를 갱신하는 방법이다. 주의해야 할 점은 waitingQueue는 비었지만 jobs에 아직 작업이 남아있는 경우가 있을 수 있다. 이때는 jobs의 첫 번째 원소의 입력 시점으로 타이머를 갱신해야 다음 작업을 진행할 수 있다. 아래의 예시를 참고하자.

jobs: {0, 5} , {0, 3} , {1, 4} , {20 , 1}

 

이 경우 0ms 시점에 waitingQueue는 다음과 같을 것이다.

timer: 0 / waitingQueue: {0, 3} , {0, 5} / jobs : {1, 4} , {20 , 1}

 

첫 번째 {0 , 3} 작업이 종료된 후인 3ms 시점에서 waitingQueue상황은 다음과 같을 것이다.

timer: 3 / waitingQueue: {1, 4} , {0, 5} / jobs : {20, 1}

 

두 번째, 세 번째 작업까지 끝난 후인 12ms 시점에서 waitingQueue는 비어있을 것이다.

timer: 12 / waitingQueue: - / jobs: {20, 1}

 

이런 상황에서는 jobs의 첫번째 요소의 입력 시점으로 timer를 갱신해주자.

timer: 20 / waitingQueue: {20, 1} / jobs : -

위 내용을 정리하면 다음과 같다.

• 처리할 작업이 있거나, 작업 대기큐가 비어있지 않다면 아래의 내용을 계속 반복한다.
  • waitingQueue에 내용이 있다면 waitingQueue의 첫 번째 원소의 작업을 처리하고 timer를 갱신한다.
  • waitingQueue가 비었다면, timer를 jobs의 다음 인덱스의 input값으로 갱신하여 입력을 받을 수 있도록 한다.
  • 갱신된 timer의 값보다 입력시점이 더 빠른 job들을 모두 waitigQueue에 삽입한다.

구현

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

using namespace std;

struct Job {
    Job()
        :input(0), processing(0)
    {}
    int input;
    int processing;
};

struct Compare {
    bool operator()(Job* left, Job* right)
    {
        return left->processing > right->processing;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    size_t jobIndex = 0;
    int timer = 0;
    int totalProcessingTime = 0;

    // 입력 받은 작업을 입력시간 기준으로 오름차순 정렬한다.
    sort(jobs.begin(), jobs.end(), 
         [](vector<int> left, vector<int>right) {
        return left[0] < right[0];
    });

    //  소요시간이 짧은 작업이 높은 우선순위를 갖도록하는 대기 큐
    priority_queue<Job*, vector<Job*>, Compare> waitingQueue;

    while (jobIndex < jobs.size() || !waitingQueue.empty()){
        // 대기큐에 작업이 있는 경우
        if (!waitingQueue.empty())
        {
            // 작업을 실행하고 타이머를 갱신한다.
            Job* finishedJob = waitingQueue.top();
            waitingQueue.pop();

            timer += finishedJob->processing;
            totalProcessingTime += timer - finishedJob->input;
            delete finishedJob;
        }
        else    // 대기 큐에 작업이 없는 경우 
        {
              //jobs의 다음 인덱스의 입력값으로 타이머를 갱신한다.
            timer = jobs[jobIndex][0]; 
        }

        // 현재 시간보다 빠른 입력시간을 가진 모든 작업을 대기큐에 입력한다.
        while (jobIndex < jobs.size() && jobs[jobIndex][0] <= timer)
        {
            Job* newJob = new Job;
            newJob->input = jobs[jobIndex][0];
            newJob->processing = jobs[jobIndex][1];
            waitingQueue.push(newJob);
            jobIndex++;
        }
    } 

    // 총 소요시간의 평균을 구한다.
    answer = totalProcessingTime / jobs.size();

    return answer;
}