프로그래머스 (디스크 컨트롤러, 힙(Heap)) C++

 

sort 정렬을 할 때 cmp를 사용해서 알고리즘을 작성했었지만 테스트 케이슬 전부 통과하지 못했다. 요청한 순서대로 추가를 하고 추가를 할 때 우선순위 큐를 이용해서 operation을 추가해서 넣으면 테스트 케이슬 모두 통과할 수 있다.

 

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

using namespace std;

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

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int task = 0;
    int time = 0;
    
    // pq에 값을 넣게 되는 경우 작업 시간이 짧은 순서대로 정렬이 된다.
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    
    // 요청 순서대로 정렬
    sort(jobs.begin(), jobs.end());
    
    while(task < jobs.size() || !pq.empty()) {
        if(jobs.size() > task && time >= jobs[task][0]) {
            pq.push(jobs[task++]);
            continue;
        }
        
        if(!pq.empty()) {
            time += pq.top()[1];
            answer += time - pq.top()[0];
            pq.pop();
        } else
            time = jobs[task][0];
    }
    
    return answer/jobs.size();
}

 

 

다음은 해당 테스트 케이스를 모두 통과한 코드

 

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

using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int time = 0;
    int sum = 0;
    
    for(int i = 0 ; i < jobs.size() ; i++) {
        int count = 0;
        int index = 0;
        
        time += jobs[i][1];
        int next = jobs[i+1][1];
        
        // 현재 시행하고 있는 것 다음부터 for문으로 돌린다.
        for(int j = i+1 ; j < jobs.size() ; j++) {
            
            // 만약 이전 시행한 시간 내에 요청이 들어온 작업이 있는 경우
            if(jobs[j][0] <= time) {
                
                // 다음 시행할 것의 작업 시간이 next보다 작은 경우
                // next를 최신화하고 index 변수에 원하는 index 값을 넣어준다.
                if(next > jobs[j][1]) {
                    count++;
                    next = jobs[j][1];
                    index = j;
                }
            }
        }
        
        // 만약 count된 것이 하나라도 존재하면 작업 시간 내에 요청이 들어온 것이
        // 2개 이상인 경우이므로 최소작업 시간을 갖는 요청을 i+1 번째와 바꿔준다.
        if(count >= 1) {
            vector<int> temp = jobs[index];
            jobs[index] = jobs[i+1];
            jobs[i+1] = temp;
        }
    }
    
    for(int i= 0 ; i < jobs.size() ; i++) {
        cout << jobs[i][0] << " " << jobs[i][1] << endl;
    }
    
    for(int i= 0 ; i < jobs.size() ; i++) {
        sum += jobs[i][1];
        answer += sum - jobs[i][0];
    }
    
    answer = answer / jobs.size();
    
    return answer;
}