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

 

 

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

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

 

" 매번 하나의 태스크가 완수될 때마다, 그 시간 안에 요청된 대기열들을 pq에 추가하고 현재 time이 증가한다."

 

라는 알고리즘은 설정을 했었는데, 코딩이 잘 안됐다.

 

 

 

반복문을 어떻게 해야 효율적으로 할 수 있는지 캐치를 못했는데

 

while 하나를 쓰고 제일 처음에 등장하는 if&continue로

 

불필요한 추가적인 반복문을 제외시킬 수 있다는 것을 알았다(아래 Reference 참고)

 

 

 

그리고 나는 pq를 설정할 때, greater를 사용하고 pair로 데이터 구조를 설정했는데

 

내가 cmp 스트럭쳐를 따로 작성하고 사용할 수도 있는 것 같다.

 

그러면 그냥 pq에 push할때 make_pair안하고 jobs[idx++]를 넣으면 된다.

 

 

Code

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

using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    sort(jobs.begin(), jobs.end());
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    int idx = 0, time = 0;
    
    while (idx < jobs.size() || !pq.empty()) {
        if(idx < jobs.size() && time >= jobs[idx][0]) {
            pq.push(make_pair(jobs[idx][1], jobs[idx][0]));
            idx++;
            continue;
        }
        
        if(!pq.empty()) {
            time += pq.top().first; // 완료된 시간
            answer += time - pq.top().second; // 기다린 시간 더해줌
            pq.pop();
        }
        
        else {
            time = jobs[idx][0];
        }
    }
    
    return answer / jobs.size();
}

 

 

Reference: https://mungto.tistory.com/15

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