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

 이 문제는 우선순위 큐(힙)를 이용해서 푸는 문제이다. 로직은 어렵지 않게 구현했지만, 계속 오류가 발생했다. input 큐를 돌면서 매번 현재 시간보다 넘어간 job들을 모두 푸시하는 부분이 문제가 없다고 판단하고 다른 곳을 고쳤으나 문제가 해결되지 않았다. 그래서 입력으로 주어진 배열을 정렬하고 제출하니 정답이 나왔다.

 사실 내가 생각한 대로라면 입력 배열의 정렬 유무와 상관없이 동작해야 한다. 하지만 tempInput.first <= second 부분에서 이 조건이 만족할 때만 input에서 pop을 하도록 구현해서, 정렬이 되어있지 않으면 input 전체를 돌지 않도록 되어있었다. 디버깅이 쉽게 가능한 백준 문제와 달리 웹 사이트 내에서 구현하는 프로그래머스 특성 상 구현할 때마다 확실히 동작하는지를 항상 생각하고 코딩을 짜야할 것 같다.

 

 

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

using namespace std;

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

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    
    sort(jobs.begin(), jobs.end());
    
    queue<pair<int, int>> input;
    
    for (vector<int> job : jobs)
    {
        input.push({job[0], job[1]});
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
    
    vector<int> temp;
    int second = 0;
    while (!(input.empty() && pq.empty()))
    {
        // 요청 시간이 된 job push
        int size = input.size();
        
        for (int i = 0; i < size; i++)
        {
            pair<int, int> tempInput = input.front();
            
            if (tempInput.first <= second)
            {
                pq.push(tempInput);
                input.pop();
            }
        }
        
        // 우선순위 큐에서 하나 pop, 만약 비어있으면 second 1 증가
        if (pq.empty())
        {
            second++;
            continue;
        }
        // 처리 로직
        pair<int, int> present = pq.top();
        pq.pop();
        
        second += present.second;
        temp.push_back(second - present.first);
    }
    
    int size = temp.size();
    double mean = 0;
    for (int t : temp)
    {
        mean += t;
    }
    mean /= size;
    answer = (int)mean;
    
    return answer;
}