프린터 (프로그래머스)

대기목록의 문서들을 순서대로 담을 큐와 가장 중요도가 높은 문서를 알 수 있도록 해주는 최대 힙이 필요한 문제였다. 

 

풀이과정을 정리해보면 다음과 같다.

1. 문서 순서와 중요도를 기록할 큐 q와 중요도가 큰 순서대로 보여줄 최대 힙 pq를 선언한다. 

2. 주어진 priorities 정보를 q와 pq에 담는다.

3. q의 값을 꺼내 pq top에 있는 값과 비교한다. 만약 같다면 pq를 pop 한다. (문서 순서가 location과 같으면 요청한 문서이므로 알고리즘을 종료한다.)

4. 만약 다르다면 q에서 꺼낸 값을 다시 집어넣는다.

5. 3, 4 작업을 q가 빌 때까지 반복한다.

6. 5번 작업이 끝난 후 pq가 pop 한 횟수가 구하는 값이 된다.

코드는 다음과 같다.

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

int solution(vector<int> priorities, int location) {
    int answer = 0;
    // 정보를 담을 큐
    queue<pair<int, int>> process;
    // 중요도를 중요순위대로 담을 최대 힙 
    priority_queue<int, vector<int>, less<int>> pq;
    // priorities의 정보를 큐와 힙에 넣는다.
    for(int i = 0; i < priorities.size(); ++i) 
    {
        process.push(make_pair(i, priorities[i]));
        pq.push(priorities[i]);
    }
    // 큐가 빌때까지
    while(!process.empty())
    {
        // 큐에서 정보를 하나 꺼낸다.
        pair<int, int> info = process.front();
        process.pop();
        // 최대 중요순위가 같다면
        if(info.second == pq.top())
        {
            // 출력되는 것이므로 answer를 하나 증가시킨다.
            pq.pop();
            ++answer;
            // 만약 출력하려고 하는 문서라면 루프를 빠져나온다.
            if(info.first == location) break;
        }
        // 최대 중요 순위가 아니면
        // 다시 큐에 넣는다.
        else process.push(info);
    }
    return answer;
}