Programers : 디스크 컨트롤러 - C++ / priority_queue 연산자 오버라이딩

김정욱·2021년 3월 10일
0

Algorithm - 문제

목록 보기
153/249

디스크 컨트롤러

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
struct compare{
    bool operator()(pair<int,int> a, pair<int,int> b){
        if(a.second == b.second) return a.first > b.first; // 오름차순 정렬
        return a.second > b.second; // 오름차순 정렬
    }
};

int solution(vector<vector<int>> jobs) {
    int ans = 0;
    int time = 0;
    int idx = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>, compare> q;
    sort(jobs.begin(), jobs.end());
    do{
        if(idx == jobs.size()) goto roop;
        while(jobs[idx][0] <= time)
        {
            q.push({jobs[idx][0], jobs[idx][1]});
            idx++;
            if(idx == jobs.size()) break;
        }
        roop:
        if(!q.empty()){
            ans += (time-q.top().first) + q.top().second;
            time += q.top().second;
            q.pop();   
        }else time = jobs[idx][0];
    }while(idx < jobs.size() or !q.empty());
    ans /= jobs.size();
    return ans;
}
  • key point!
    작업의 요청부터 종료까지 걸린 최소시간
    --> 해당 시간까지 들어온 요청중 작업시간이 짧은 것부터 실행했을 때!
  • 깨달은 것
    : priority_queue<pair<int,int>> 특정compare함수 만드는 법
/* 구조체로 만들고 나서 넣어줘야 함! */
struct compare{
    /* 연산자 오버라이딩 */
    bool operator()(pair<int,int> a, pair<int,int> b){
        if(a.second == b.second) return a.first > b.first; // 오름차순 정렬
        return a.second > b.second; // 오름차순 정렬
    } // sort()의 compare와 반대로 짜줘야함
};

priority_queue<pair<int,int>,vector<pair<int,int>>, compare> q;

: struct로 구조체 만든 후 연산자 오버라이딩

  • compare함수 비교
    • sort의 compare
      • retrurn true -> swap
      • return false -> 그대로
      • 첫번째 파라미터 -> next value
      • 두번째 파라미터 -> current value
    • 연산자 오버라이딩 compare
      • return true -> 그대로
      • return false -> swap
      • 첫번째 파라미터 -> current value
      • 두번째 파라미터 -> next value
profile
Developer & PhotoGrapher

0개의 댓글