프린터 - 프로그래머스, c++

 

 

- 문제 풀이

"우선순위 큐"를 사용하는 문제였다.

1. 우선순위 큐를 사용하려면 #include <queue>를 한 후 priority_queue<int> pq; 형태로 선언해주면 된다.

2. 그 외에도 문제에 필요한 큐 q, 변수들을 선언한다.

    우선순위 큐(pq)는 하나의 int값만 있고 그 int값에 따라 sort되기 때문에 여러 변수를 넣지 못한다.

    이 문제를 해결하기 위해 또 다른 큐(q)를 사용해야 했다. 

    이 큐(q)에는 vector "priorities"의 index와 value를 pair로 만든 것을 저장한다.

3. 우선순위 큐(pq)에는 vector "priorities"의 value를 넣어 우선순위대로 정렬되도록 한다.

4. while문을 통해 큐(q)가 비어있을 때까지 돌며 우선순위 큐(pq)에서 정렬된 우선순위 순서대로 큐(q)의 값을 빼낸다.

    (처음에 큐(q)값 빼내고 우선순위의 값과 같지 않다면 다시 push해서 넣음)

    만약 값이 같다면 큐(q)에서 값을 빼낸 상태로 두고 우선순위 큐(pq)의 값을 빼낸다. count도 하나 증가시키기

    또 그 값의 index와 주어진 location이 같다면 count값을 반환하며 반복문을 종료한다.

 

 

- 코드

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

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int count = 0;
    queue <pair<int,int>> q;
    priority_queue <int> p_q;
    
    for(int i=0; i<priorities.size(); i++) {
        q.push(make_pair(i, priorities[i]));
        p_q.push(priorities[i]);
    }
    
    while(!q.empty()) {
        int index = q.front().first;
        int value = q.front().second;
        q.pop();
        if(value == p_q.top()) {
            p_q.pop();
            count++;
            if(index == location) {
                answer = count;
                break;
            }
        }
        else {
            q.push(make_pair(index, value));
        }
    }
    
    return answer;
}