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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

힙 Heap, 우선순위 큐 Priority Queue

 

---

 

 

정답코드

 

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

bool Compare(const vector<int>& a, const vector<int>& b) {
    if (a[1] == b[1]) return a[0] < b[0]; // 소요 시간이 같으면 요청 시간이 작은 순으로 정렬
    return a[1] < b[1]; // 소요 시간이 작은 순으로 정렬
}

int solution(vector<vector<int>> jobs) {
    int n = jobs.size(); // 작업의 수
    sort(jobs.begin(), jobs.end(), Compare);
    
    int time = 0;  // 총 소요 시간
    int start = 0; // 현재 시각

    while (!jobs.empty()) 
    {
        // 현재 시각(start)에서 처리 가능한 작업을 찾음
        for (int i = 0; i < jobs.size(); i++) 
        {
            if (jobs[i][0] <= start) { // 작업 요청 시간이 현재 시각보다 작거나 같은 경우
                time += start + (jobs[i][1] - jobs[i][0]); // 총 소요 시간을 갱신
                start += jobs[i][1]; 					   // 현재 시각을 작업의 소요 시간만큼 더함
                jobs.erase(jobs.begin() + i); 			   // 작업 리스트에서 해당 작업을 제거
                break; 									   // 작업을 처리했으므로 for문을 나감
            }

            if (i == jobs.size() - 1) start++; // 만약 현재 시각에서 처리 가능한 작업이 없다면 시각을 1 증가(남아 있는 job 들이 모두 start 보다 뒤에 시작된다는 뜻. 따라서 다음 번 job 이 시작 할 때까지 ++)
        }
    }

    return time / n; // 평균 대기 시간을 반환
}

int main(){
    vector<vector<int>> testcase1 = { {0, 3}, {1, 9}, {2, 6} };
    vector<vector<int>> testcase2 = { {24, 10}, {18, 39}, {34, 20}, {37, 5}, {47, 22}, {20, 47}, {15, 2}, {15, 34}, {35, 43}, {26, 1} };

    cout << solution(testcase1) << "\n"; // 9
    cout << solution(testcase2) << "\n"; // 74

    return 0;
}

 

---

 

 

정답코드2 - priority_queue

 

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

struct Compare {
    bool operator()(const vector<int>& a, const vector<int>& b) {
        return a[1] > b[1]; // 소요 시간이 작은 순으로 정렬
    }
};

int solution(vector<vector<int>> jobs) {
    int n = jobs.size();
    sort(jobs.begin(), jobs.end()); // 요청 시간 기준으로 정렬

    priority_queue<vector<int>, vector<vector<int>>, Compare> pQ;
    int answer = 0, i = 0, time = 0;

    while (i < jobs.size() || !pQ.empty()) 
    {
        // 현재 시간에서 실행 가능한 모든 작업을 큐에 넣음
        while (i < jobs.size() && time >= jobs[i][0]) {
            pQ.push(jobs[i++]);
        }

        if (!pQ.empty()) { 
            vector<int> job = pQ.top();
            pQ.pop();
            time += job[1];              // 작업 소요 시간을 더함
            answer += time - job[0];     // 작업 종료 시간 - 작업 요청 시간 = 대기 시간
        } 
        else {
            time = jobs[i][0];           // 다음 작업의 요청 시간으로 시간 설정
        }
    }

    return answer / n; // 평균 대기 시간 반환
}

 

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

struct Compare {
    bool operator()(const vector<int>& a, const vector<int>& b){
        if (a[1] == b[1]) return a[0] > b[0];
        return a[1] > b[1];
    }
};

int solution(vector<vector<int>> jobs) {
    int n = jobs.size();
    sort(jobs.begin(), jobs.end());
    
    priority_queue<vector<int>, vector<vector<int>>, Compare> pQ;
    
    int time = 0, total = 0, idx = 0;
    while (idx < n || !pQ.empty())
    {
        for (int i = idx; i < n; i++){
            if (jobs[i][0] <= time){
                pQ.push(jobs[i]);
                idx++;
            }
            else{
                break;
            }
        }
        
        if (!pQ.empty()) // 대기 중인 작업이나 현재 바로 시작할 작업이 있는 경우 
        {
            time += pQ.top()[1];
            total += time - pQ.top()[0];
            pQ.pop();
        }
        else { // 현재 time 기준 시작할 수 있는 작업이 없는 경우 
            if (idx < n) {
                time = jobs[idx][0];  
            } 
        }        
    }
    
    return total / n;
}

---