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

문제 링크

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

 

 

 

풀이

문제를 보고 종료시점이 핵심이라는 것을 알고 우선순위 큐를 적용했다.

종료 시점에서 (요청시간<=종료시점)인 경우에 작업 소요시간이 가장 적은 작업을 먼저 수행하면 된다.

 

요약하자면,

-> 요청~종료 시간의 합 평균을 줄이기 위해서는 작업들의 대기시간을 줄여야 한다.

-> 작업들의 대기시간을 줄이기 위해서는 작업을 할 수 있을 때, 작업의 수를 줄여야 한다.

-> 작업의 수를 빠르게 줄이기 위해서는 작업을 할 수 있을 경우에 소요 시간이 작은 것을 먼저 하면 된다.

 

따라서, 코드 작성은 종료시점을 기록하면서 종료시점에서 작업을 할 수 있는 목록 중 소요시간이 가장 작은 작업을 먼저하면 된다.

이를, 작업을 할 수 있는 목록을 우선순위 큐(Priority_Queue)를 이용하면 편리하다.

 

// init

문제에서 요청 시간이 오름차순 정렬돼 있다고 명확하지 않으므로 혹시 모르기 때문에 오름차순 정렬을 해주었다.

(stable_sort: 합병정렬을 써보았다. 어느 정렬이든 상관없다.)

i는 jobs의 인덱스

end는 종료시점

우선순위 큐 선언(정렬방법을 직접 cmp구조체의 연산자 오버로딩으로 정의해준다)

- 정렬 순서

  1. 소요시간이 작은게 먼저 나오도록

  2. 소요시간이 같을 경우 요청시간 작은 것이 먼저 나오도록

 

// process

반복문을 true

{

    if(요청시점 <= 종료시점)인 모든 작업들을 우선순위 큐(pq)에 push

 

    if 작업 목록(pq)에 작업이 없을 경우 검사

        1. 더 이상 남은 작업이 없는 경우 -> break;

        2. 아닌 경우 -> 종료 시점을 제일 빠른 요청 시간으로 건너뜀

 

    종료 시점 갱신(end)

    요청~종료시간 카운팅(answer)

}

리턴은 평균이므로 jobs.size()로 나눠준다(소수점 버림)

 

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

using namespace std;

// [요청 시점, 소요시간] jobs

struct cmp{
    bool operator()(vector<int> v1, vector<int> v2){
        if(v1[1] == v2[1]) return v1[0] > v2[0];  // 같을 경우, 요청시간 작은 것으로
        return v1[1] > v2[1];       // 소요 시간 작은게 먼저 나오도록
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    
    // init
    stable_sort(jobs.begin(), jobs.end());        // 요청 시간으로 오름차순 정렬
    int i=0;
    int end=jobs[i][0];
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;

    // process
    while(true){
        for(; i<jobs.size(); i++){
            if(jobs[i][0] > end) break;
            pq.push(jobs[i]);      // 요청 시점 <= 종료 시점
        }
        if(pq.empty()){
            if(i==jobs.size()) break;
            end = jobs[i][0];      // 먼저 요청 들어온 작업부터
            continue;
        }
        int req = pq.top()[0];
        int time = pq.top()[1];
        pq.pop();
        end += time;        // 종료 시점 갱신
        answer += end-req;        // 요청부터 종료까지 소요시간 카운팅
    }
    
    return answer/jobs.size();      // 요청~종료 합 평균 최소값 리턴(소수점 버림)
}