[프로그래머스]힙(Heap) : 디스크 컨트롤러 (level 3) (c++)

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

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

 

 

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

using namespace std;

struct work {
    int in, w_time;
};

struct compare {
    bool operator()(work& a, work& b)
    {
        return a.w_time > b.w_time;
    }
};

int solution(vector<vector<int>> jobs) {

    // 요청시각 오름차순으로 정렬
    sort(jobs.begin(), jobs.end());

    // 작업을 작업시간 오름차순으로 정렬하는 우선순위 큐
    priority_queue<work, vector<work>, compare> q;

    int N = jobs.size();
    int now = 0, cnt = 0, t_stay = 0, done = 0;

    // 모든 작업을 마칠 때까지 반복문
    while (N - done)
    {
        // 아직 추가하지 않은 작업물 부터 반복문
        for (int i = cnt; i < N; ++i)
        {
            // 현재 이전에 요청받은 작업물이 있다면 모두 큐에 추가
            if (jobs[i][0] <= now)
            {
                q.push({ jobs[i][0], jobs[i][1] });
                ++cnt;
            }
            /*
                현재 이전에 요청받은 작업물은 없지만
                큐가 비어있다면 작업물 하나 추가 후 
                현재 시각을 해당 작업 요청시각으로 변경
            */
            else if (q.empty())
            {
                q.push({ jobs[i][0], jobs[i][1] });
                ++cnt;
                now = jobs[i][0];
                break;
            }
        }

        work w = q.top();
        q.pop();

        now += w.w_time;        // 현재시각 : 이번 작업물을 끝마친 시각
        t_stay += now - w.in;   // t_stay에 대기시간(현재 - 작업물 요청시각) 추가 
        ++done;
    }

    return t_stay / N;
}

 

 

TIP1

우선순위 큐의 정렬기준은 sort() 함수의 compare functor와는 조금 다르다.

알고리즘 풀이 기준에서 가장 큰 차이점은

정렬 기준이 첫번째 인자가 아니라 두번째 인자 기준이라는 것이다. 

// cat을 기준으로 하는 오름차순 정렬이다. 내림차순 아님
struct compare {
    bool operator()(dog& a, dog& b)
    {
        return a.cat > b.cat;
    }
};

위처럼 두번째 인자 b를 기준으로 했을 때, a보다 작으면 true이기 때문에 

위 구조체는 cat 오름차순 정렬로 비교연산자를 재정의한 코드가 된다. 

 

 

 

TIP2

문제 구현 정렬기준은 문제에서 원하는 그대로 잡으면 된다.

작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리

 

즉, work_A가 먼저 처리하는 경우의 총 대기시간과

work_B를 먼저 처리하는 경우의 총 대기시간을 비교하면 된다. 

식이 복잡할 것 같지만 정리해나가보면 간단해진다.

 

현재로부터 두 작업을 진행했을 때 걸리는 시간

// A -> B 순으로 작업할 때  
(현재 + A.w_time - A.in) + (현재 + A.w_time + B.w_time - B.in) 

// B -> A 순으로 작업할 때  
(현재 + B.w_time - B.in) + (현재 + B.w_time + A.w_time - A.in) 

 

두 식을 비교하는 식

(현재 + A.w_time - A.in) + (현재 + A.w_time + B.w_time - B.in)  
        > (현재 + B.w_time - B.in) + (현재 + B.w_time + A.w_time - A.in)

 

위 식에서 양변 공통 사항을 소거하면..

A.w_time > B.w_time		

짠!

 

 

 

 

* 우선순위 큐에 대해 참고한 페이지들

 

우선순위 큐 레퍼런스 문서 

std::priority_queue - cppreference.com

우선순위 큐 comparator에 대해 좀더 자세한 정보

declaring a priority_queue in c++ with a custom comparator

우선순위 큐의 비교연산자 재정의에 대해 쉽게 설명한 한국어 블로그들

c++ priority queue 예제 : compare 구조체만 잘 정의합시다.

 

STL priority queue 활용법