문제가 쉬운 것 같으면서도 쉽게 안풀렸다....
우선순위큐와 그냥 큐 두 개를 준비한다.
[2, 1, 3, 2] 를 예시로 들자면,
우선순위큐 -> 3 2 2 1
그냥 큐(q) ->
0 1 2 3(인덱스)
2 1 3 2(priorities)
pair을 써줬는데, q.front().first
인 경우 0이고,
q.front().second
인 경우 2가 된다.
우선순위 큐와 큐의 두 번째 요소가 같아질때까지 넣었다 빼는걸 반복한다
2 3 0 1(인덱스)
3 2 2 1(priorities)
이렇게 정리가 되면 인덱스와 location이 같아질때까지 개수를 센다.
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int solution(vector<int> priorities, int location) {
int answer = 0;
priority_queue<int> pq;
queue<pair<int, int>> q;
for(int i=0;i<priorities.size();i++){
q.push(make_pair(i,priorities[i]));
pq.push(priorities[i]);
}
while(!q.empty()){
int i = q.front().first;
int p = q.front().second;
q.pop();
if(p == pq.top()) {
pq.pop();
answer += 1;
if(i == location) {
break;
}
} else {
q.push(make_pair(i,p));
}
}
return answer;
}