[Algorithm] 프로그래머스 프린터 - C++, 큐, 우선순위 큐

코딩테스트 연습 - 프린터

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

int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue<int> pq;
    queue<pair<int, int>> q;  // priority, index

    for(int i = 0; i < priorities.size(); i++){
        pq.push(priorities[i]);
        q.push(make_pair(priorities[i], i));
    }

    while(!q.empty()){
        int curPirority = q.front().first;
        int curIndex = q.front().second;
        q.pop();

        if(curPirority == pq.top()){
            pq.pop();
            answer++;

            if(curIndex == location)
                break;
        }
        else{
            q.push(make_pair(curPirority, curIndex));
        }
    }

    return answer;
}

---

 큐를 쓰는거 같기는 했는데 어떤 식으로 변형해야할지 애매한 문제였습니다. 단일 큐를 사용하면 이게 남은 작업물들 중 어느정도의 우선순위인지를 모르고 우선순위 큐를 사용하면 location을 정렬하기가 애매했습니다.

 그래서 우선순위 큐를 통해서 전체 작업물의 '우선도'를 저장해두고 큐에서 하나하나 빼보면서 비교하는 것입니다. 비교를 했을때 우선도가 같다면 이 작업물을 하는게 맞으니 출력을 하고 index 비교를 해보는 것이죠.