힙(Heap)

디스크 컨트롤러

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

using namespace std;

struct cmp{
    bool operator() (pair<int, int> a, pair<int, int> b) {
        return a.second >= b.second;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int jobs_size = jobs.size();
    int times = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> can_work_list;

    sort(jobs.begin(), jobs.end(), [] (vector<int> a, vector<int> b) {return a[0] > b[0];});

    while (jobs.size() + can_work_list.size()) {
        if (can_work_list.empty() && jobs.back()[0] > times) times = jobs.back()[0];

        while (!jobs.empty() && jobs.back()[0] <= times) {
            can_work_list.push({jobs.back()[0], jobs.back()[1]});
            jobs.pop_back();
        }

        auto now_working = can_work_list.top();
        can_work_list.pop();

        times += now_working.second;
        answer += times - now_working.first;
    }

    return answer / jobs_size;
}

정확성  테스트
  테스트 1 〉	통과 (0.37ms, 3.96MB)
  테스트 2 〉	통과 (0.31ms, 3.82MB)
  테스트 3 〉	통과 (0.27ms, 3.94MB)
  테스트 4 〉	통과 (0.24ms, 3.71MB)
  테스트 5 〉	통과 (0.31ms, 3.97MB)
  테스트 6 〉	통과 (0.02ms, 3.95MB)
  테스트 7 〉	통과 (0.23ms, 3.96MB)
  테스트 8 〉	통과 (0.19ms, 3.97MB)
  테스트 9 〉	통과 (0.06ms, 3.97MB)
  테스트 10 〉	통과 (0.40ms, 3.94MB)
  테스트 11 〉	통과 (0.01ms, 3.94MB)
  테스트 12 〉	통과 (0.01ms, 3.96MB)
  테스트 13 〉	통과 (0.02ms, 3.9MB)
  테스트 14 〉	통과 (0.01ms, 3.95MB)
  테스트 15 〉	통과 (0.01ms, 3.97MB)
  테스트 16 〉	통과 (0.01ms, 3.96MB)
  테스트 17 〉	통과 (0.01ms, 3.95MB)
  테스트 18 〉	통과 (0.01ms, 3.96MB)
  테스트 19 〉	통과 (0.01ms, 3.78MB)
  테스트 20 〉	통과 (0.01ms, 3.96MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0

이중우선순위큐

#include <string>
#include <vector>
#include <list>

using namespace std;

vector<int> solution(vector<string> operations) {

    list <int> num_list;

    for (int i=0; i<operations.size(); i++) {
        switch (operations[i][0]) {
            case 'I':
                num_list.push_back(stoi(operations[i].replace(0, 2, "")));
                num_list.sort();
                break;
            case 'D':
                if (!num_list.empty()) {
                    if (operations[i] == "D 1") {
                        num_list.pop_back();
                    } else if (operations[i] == "D -1") {
                        num_list.pop_front();
                    }
                }
                break;
        }
    }
    
    if (num_list.empty()) return {0, 0};
    else return {num_list.back(), num_list.front()};
}

정확성  테스트
  테스트 1 〉	통과 (0.02ms, 3.97MB)
  테스트 2 〉	통과 (0.02ms, 3.96MB)
  테스트 3 〉	통과 (0.02ms, 3.95MB)
  테스트 4 〉	통과 (0.01ms, 3.71MB)
  테스트 5 〉	통과 (0.02ms, 3.96MB)
  테스트 6 〉	통과 (0.04ms, 3.96MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0