프로그래머스 - 프린터

programmers.co.kr/learn/courses/30/lessons/42587?language=cpp#

코딩테스트 연습 - 프린터

 

1. 우선순위 큐를 이용해 높은 수가 앞으로 오도록 한다 (기본 max heap)

2. 큐를 pair 타입으로 선언하여 인덱스와 값을 갖도록 해준다

3. 큐에서 하나씩 빼내고, 우선순위 큐의 top 과 동일한 값이면 우선순위가 일치하는 것이므로 카운팅을 하나 늘리고, 만약 그 일치하는 값의 인덱스 마저도 같으면 문제에서 요구하는 값이므로 리턴시킨다.

4. 우선순위 큐의 top 과 일치하지 않으면 우선순위가 뒤로 밀려야하므로, 큐의 뒤에 다시 push 한다.

 

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
int solution(vector<int> priorities, int location) {
    int answer = 0, size = priorities.size();
   
    priority_queue<int> pq; // value
    queue<pair<int, int>> q; // index, value
    for (int i = 0; i < size; ++i) {
        q.push(make_pair(i, priorities[i]));
        pq.push(priorities[i]);
    }
    
    while(!q.empty()) {
        int idx = q.front().first;
        int val = q.front().second;
        q.pop();
        
        if (pq.top() == val) {
            answer++;
            pq.pop();
            if (idx == location) {
                return answer;
            }
        } else {
            q.push(make_pair(idx, val));
        }
    }
    return answer;
}