[C++/PGS] Lv.3 : 디스크 컨트롤러 (Heap/priority_queue)

 

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

프로그래머스

---

프로그래머스 레벨 3.

SJF 스케줄링 기법을 구현하는 문제이다!

생각보다 까다롭고, 힙 정렬 커스텀 관련한 문법을 알고 있어야 해서 약간 어려웠다

 

우선순위에 따라서 자동 정렬이 되어야하는데, 그래서 처음에는 정렬이 가능한 Map으로 풀다가

시간이 될때마다 가능한 작업을 삽입해주는 형식이 맞다는 걸 깨달아서 Queue로 바꾸었다.

 

우선순위 큐를 사용해서, 해당 시간이 될 때마다 데이터를 삽입하고 기준에 맞게 정렬해야 한다!

데이터 크기나 시간 값에 대한 조건 등이 그렇게 크지 않아서,

반복문을 돌릴 때마다 1초씩 흐른다고 가정하고 풀었다.

 

 

priority_queue를 선언할 때,

일반적인 최대 힙 사용 시에는 "priority_queue<vector<int>>" 로 사용하면 되는데

 

최소 힙을 쓸 때나 정렬함수를 커스텀하려면

"priority_queue<vector<int>, vector<vector<int>>, compare>"

이렇게 복잡하게 써야하는 걸 처음 알았다.

 

왜 그러나 했더니, 값을 담아서 정렬할 컨테이너가 필요한 거였다,,, ㅎ.ㅎ

기억해두기!!

 

 

나의 풀이

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

struct cmp{
    bool operator()(vector<int> &a, vector<int> &b){
        if(a[0]==b[0]) return a[1] > b[1];
        return a[0] > b[0];
    }
    // 바꿀래?라고 물을 때, true -> 바꾼다
};

int solution(vector<vector<int>> jobs) { // [요청 시각, 소요시간]
    // 비선점 sjf
    int answer = 0;
    vector<int> returnTime;
    priority_queue<vector<int>, vector<vector<int>>, cmp> schedule;
    // 소요시간, 요청시간 - cmp 정렬 함수 사용
    sort(jobs.begin(), jobs.end());
    
    int time = 0; // 현재 시간
    int index = 0; // jobs 인덱스
    int isRunning = 0;
    while(!schedule.empty() || index < jobs.size()){
        // 1. 시간이 될때마다 큐에 삽입
        if(index < jobs.size() && time >= jobs[index][0]){
            vector<int> v;
            v.push_back(jobs[index][1]); v.push_back(jobs[index][0]);
            schedule.push(v);
            index++;
        }
        // 2. 실행중인 상태가 아닐 때, 큐 top을 꺼내서 실행
        if(isRunning==0 && !schedule.empty()){
            vector<int> v = schedule.top();
            schedule.pop();
            // 반환시간 = 종료 시각 - 요청 시각
            returnTime.push_back(time+v[0]-v[1]);
            // cout << time+v[0]-v[1]<<"\n";
            isRunning = v[0]; // 소요시간 동안 true인 상태
        }
        time++;
        if(isRunning>0) isRunning--;
    }
    for(int n:returnTime){
        answer += n;
    }
    answer /= returnTime.size();
    return answer;
}