Programmers : 프린터

풀이 상세

큐

풀이 요약

1. 해당 인덱스가 몇번째에 나오는지 파악하기 위해서, pair 를 통해 인덱스와 함께 큐에 넣었다.

2. 현재 큐의 가장 높은 우선순위를 구한 후, 큐의 맨앞의 값이 가장 높은 우선순위가 아니라면 빼서 맨 뒤에 넣어준다.

3. 만약 큐의 맨앞의 값이 가장 높은 우선순위라면, 이를 큐에서 뺀 후, 이를 확인하여 원하는 인덱스인지를 확인한다. 인덱스가 아니라면 다시 남은 것 가운데 가장 높은 우선순위를 구하고, 맞다면 지금까지 큐를 뺀 횟수를 반환한다.

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

void maxPriority(vector<int> &v) {
    MAX = 0;
    for(int i=0; i<v.size(); i++) {
        MAX = max(MAX, v[i]);
    }
}

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int, int>> q;
    for(int i=0; i<priorities.size(); i++) {
        q.push({i, priorities[i]});
    }
    maxPriority(priorities);

    while(!q.empty() && MAX != 0) {
        pair<int,int> curr = q.front();
        q.pop();
        if(curr.second != MAX) {
            q.push(curr);
        } else {
            answer++;
            if(curr.first == location) return answer;
            priorities[curr.first] = -1;
            maxPriority(priorities);
        }
    }
}