프린터

들어가는 말

프린터에서 우선순위 대로 문서를 출력한다. 이때 지정된 위치에 있는 문서는 몇 번째에 출력되는지 구하라. 숫자가 클수록 우선순위가 높다는 것을 조심하라.

보자마자 큐로 풀어야겠다고 생각했다. 그러나, 핵심에서 막혔는데 우선순위 큐로 pair을 돌리면 같은 숫자를 처리하지 못해서 바른 위치가 나오지 않는 거다. 참고한 블로그에서는 우선순위와 위치를 넣은 큐와 우선순위만을 넣은 우선순위 큐를 만들라고 했다. 우선순위 큐와 그냥 큐의 우선순위를 서로 비교해서 푸는 거다.

코드 설명

먼저 일반 큐하고 우선순위 큐에 값을 넣어준다. 일반 큐에는 주어진 우선순위와 위치를 pair로 집어넣는다. 그리고 우선순위 큐에는 주어진 우선순위를 내림차순으로 정리해서 넣어준다.

다음 우선순위 큐가 빌 때까지 while을 돌려주는데, c에다가는 주어진 우선순위를 c_location에는 주어진 우선순위의 위치를 넣어준다. 여기서 주의할 점은 q.pop()을 해야 한다는 거다. 왜냐하면 우선순위가 같지 않을 경우 앞의 문서를 뒤로 넣어줘야 하기 때문이다. 게다가 뒤의 문서를 확인해야 하기 때문에 무조건 pop을 해줘야 한다!!!

그래서 현재 우선순위와 실제 우선선위가 같다면 문서가 출려되는 거니 count++을 해주고 현재 우선순위를 pop해준다. 우선순위도 같은데 위치 또한 같다면 원하는 문서가 출력된 것이니 count를 answer에 넣어주고 break를 해주면 된다. 만일 위치가 같지 않다면 다시 우선순위를 비교해주면 된다. 만일 우선순위가 다르다면 어떻게 할까 현재 우선순위 c와 현재 우선순위의 위치인 c_location을 다시 q에 넣어주면 된다.

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int, int>> q;
    priority_queue<int> pq;
    int c = 0;
    int c_location = 0;
    int count = 0;
    
    /*큐하고 우선순위 큐 넣기*/
    for(int i=0; i<priorities.size(); i++){
        q.push(make_pair(priorities[i], i));
        pq.push(priorities[i]);
    }
    
    while(!pq.empty()){
        c = q.front().first;
        c_location = q.front().second;
        q.pop();
        
        if(c == pq.top()){
            count++;
            pq.pop();
            
            if(location == c_location){
                answer = count;
                break;
            }
        }else{
            q.push(make_pair(c, c_location));
        }
    }

    
    return answer;
}