[고득점 KIT] 프린터 cpp

문제
인쇄 대기목록의 가장 앞에있는 문서를 꺼내고 나머지 인쇄 대기목록에서 중요도가 높은 문서가 있다면 맨 뒤에넣고 중요도가 높은 문서를 출력한다. 만약 중요도가 높은 문서가 없다면 그대로 출력한다.
이때 내가 원하는 문서가 몇 번째로 출력되는지 구하라

입력
문서의 중요도가 담긴 배열과 내가 뽑고자 하는 문서가 몇 번째에 있는지 입력된다.

출력
내가 출력하고자 하는 문서가 몇 번째로 출력되는지 구하라.

---

접근

각 문서에는 중요도가 있고 중요도가 높은 문서가 먼저 출력이된다. 여기서 본인이 원하는 문서가 몇 번째로 출력되는지 구해야한다. 그래서 출력되는 문서들이 몇 번째 있던 문서인지 알아야했다.

그리고 출력되는 문서가 현재 대기목록 중 가장 큰 문서인지도 확인해야했다.

 

따라서 큐에 문서의 중요도와 몇 번째있던 문서인지를 대입하였고 입력된 priorities를 내림차순 정렬하여 비교하도록 하였다. 만약 큐에 가장 앞에있는 문서와 priorities의 문서가 일치하고 내가 뽑고자하는 문서라면 반복문을 종료하도록 하였다.

 

구현

큐에 문서의 중요도와 자리를 함께 넣는다.

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

 

입력된 문서의 중요도를 내림차순으로 정렬하여 중요도가 높은 문서가 먼저 출력되도록 한다.

    sort(priorities.begin(), priorities.end(), greater<int>());

 

while문으로 비교를 한다.

먼저 큐에서 원소들을 꺼내고 현재 문서의 중요도와 가장 높은 중요도와 비교해서 같다면 idx를 증가시키고 이 문서가 내가 원하는 문서라면 while문을 종료시킨다.

그런데 현재 문서가 가장 높은 중요도를 갖지않는다면 다시 큐에 넣는다.

이 과정을 반복하면 내가 원하는 문서가 몇 번째에 나오는지 알 수 있다.

    int idx = 0;
        while(1){
        int paper = q.front().first;
        int order = q.front().second;
        q.pop();
        
        if(paper == priorities[idx]){
            idx++;
            if(order==location){
                break;
            }
            
        }
        else{
            q.push({paper, order});
        }
            
        
    }

---

전체 코드

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

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({priorities[i],i});
    }
    sort(priorities.begin(), priorities.end(), greater<int>());
    
    int idx = 0;
        while(1){
        int paper = q.front().first;
        int order = q.front().second;
        q.pop();
        
        if(paper == priorities[idx]){
            idx++;
            if(order==location){
                break;
            }
            
        }
        else{
            q.push({paper, order});
        }
            
        
    }
    answer = idx;
    return answer;
}