[프로그래머스] 디스크 컨트롤러 - 우선순위큐,힙 / C++

euneun·2021년 5월 25일

알고리즘

목록 보기

3/12

✅ 프로그래머스 디스크 컨트롤러
문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42627
작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요.

우선순위 큐

우선순위 큐란 ❓
우선순위에 따라 정렬된 큐!
원소가 삽일될때, 정의된 우선순위에 맞춰서 큐가 정렬✓된다

✓ Heap 자료구조이기 때문에, 이 정렬과정은 O(logN)의 시간복잡도를 가진다.

선언

#include <queue>

priority_queue <자료형,컨테이너,비교함수> 변수명;

//이 문제에서는
priority_queue< vector<int>, vector< vector<int> >, compare> pq;

첫번째 인자는 큐에 담을 자료형을 명시하고,
두번째 인자인 컨테이너는 보통 vector<자료형>으로 사용한다!

이 문제에서는 2차원 벡터에서 jobs벡터 하나하나(ex) [0,3])를 우선순위큐에 넣어서 사용할것이므로 vector<int>를 자료형으로 잡고, 컨테이너는 vector<vector<int>>로 잡아서 사용한다.

비교 구조체 정의하기

이 부분이 까다롭다!

위 문제에서는 작업의 소요시간을 기준으로 오름차순으로 정렬을 하며 큐에 집어넣어야지 최종 답이 최소가 되므로 오름차순으로 정렬을 해야한다.

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

compare구조체를 정의한후에 operator() 메소드를 재정의해야한다.

인자를 두개받는데, 우선순위큐를 정의한 자료형에 해당하는 인자를 두개받는다.
이 문제에서는 vector가 우선순위큐의 자료형이므로 vector<int>형의 인자 두개를 받는다.

sort함수에서 사용하는 compare를 정의하는것과 다를것이 없는데 둘 사이의 큰 차이점은

sort : 첫번째인자 기준
priority queue : 두번째인자 기준
이라는것이다!

이제 vector를 인자로 받았으니 vector의 인덱스 1에 해당하는 원소가 작업의 소요시간에 해당하므로,

return a[1] > b[1];

a[1]과 b[1]을 비교하여, 두번째 인자가 기준이었으므로 a[1]>b[1]이 true가 되는것은 오름차순 상황임을 알 수 있다.

문제 풀이 방법

작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄일 수 있는 방법은, 소요시간이 짧은것부터 처리하는 것이다!

따라서 주어진 jobs를 요청시간 오름차순으로 정렬한후,
소요시간 오름차순으로 jobs를 넣어주는 우선순위큐를 선언하면 된다.

(1)

큐에들어간 작업개수가 주어진 작업개수보다 작고
큐에 넣으려고하는 작업의 요청시간이 현재 소요된 시간보다 작을때에는

큐에 작업들을 push한다 (우선순위큐가 알아서 오름차순으로 정렬해줌)

(2) 큐에 작업이 있을때에는 소요시간이 적은순으로 pop하여 (우선순위큐가 알아서 소요시간이 적은걸 먼저 pop해줌)

현재까지 소요된 시간에, 작업의 소요시간을 넣어주고

current_time += pq.top()[1];

현재까지 소요된 시간에서 pop한 작업의 요청시점을 빼서 작업의 요청부터 종료까지 걸린 총시간을 구하여 더해나간다.

total_time += current_time - pq.top()[0];

(3) 큐에 작업이 없을경우에는, 다음작업이 요청되는 시간으로 현재 소요시간을 변경한다.

current_time = jobs[task_cnt][0];

: 수행할 작업이 현재 없을 경우에는, 다음에 우선순위 큐에 들어올 jobs의 요청시간까지 기다려야하므로, 현재시간을 변경해준다!

jobs를 요청시간 기준 오름차순으로 정렬해야지 기다리는시간이 최소가 된다! 이래서 요청시간 기준 오름차순으로도 정렬해줘야한다!
(sort(jobs.begin(), jobs.end());)

💬 테스트케이스에서는 (3)번 과정을 알 수 없었어서 좀 오래걸렸다..ㅜㅜ

(1)~(3)의 과정을 큐가 비어있지 않을동안 또는 주어진 작업개수만큼 큐에 넣었을때동안 반복한다.

전체 코드

주석 참고해서 이해하시면 좋을 것 같아요 :)

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

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

//우선순위큐에서 우선순위를 재정의하는 compare 구조체, sort와 반대임
struct compare {
    bool operator()(vector<int> a, vector<int> b) {
        return a[1] > b[1]; // 정렬 기준이 첫번째 인자가 아닌 두번째 인자 기준임. 따라서 오름차순 정렬임.
    }
};
 
int solution(vector< vector<int> > jobs) {
    
    int total_time = 0; //각 작업의 요청부터 종료까지 걸린 시간을 더해나갈 변수 선언
    
    priority_queue< vector<int>, vector< vector<int> >, compare> pq; // 소요시간을 기준으로 오름차순 정렬
    
    int current_time = 0;   // 현재 시각
    int task_cnt = 0;   // 우선순위 큐에 들어간 작업의 개수 축적
    
    sort(jobs.begin(), jobs.end()); // 요청시점을 기준으로 오름차순 정렬 (작업 요청시점이 빠른 순으로 정렬)
 
    while (task_cnt < jobs.size() || !pq.empty()) {
       
        if (task_cnt < jobs.size() && jobs[task_cnt][0] <= current_time) { //요청시간이 현재 소요된 시간보다 작을때 작업을 수행할 수 있음
            pq.push(jobs[task_cnt++]);//넣으면 소요시간이 적은 순으로 저장됨
            continue;
        }
 
        // 수행할 작업이 있는 경우
        if (!pq.empty()) {
            current_time += pq.top()[1]; //소요시간
            total_time += current_time - pq.top()[0]; //요청시점
            pq.pop();
        }
        // 수행할 작업이 없고, 현재시간 안에 들어온 작업이 없을 경우
        else {
            // 다음 작업이 들어오는 시각으로 변경
            current_time = jobs[task_cnt][0];
        }
    }  
 
    return total_time/jobs.size();  // 평균 시간 반환
}