백준 1966 프린터 큐 c++ [컴공과고씨]

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

queue를 이용하여서 풀 생각을 하였다. 해결 방식은 먼저 큐하나에는 우선 순위만 저장하고 다른 큐에는 pair를 이용하여 배열 번호와 우선 순위를 적어주었다. 그 다음 우선순위를 오름차순으로 sort를 한다.

그 후 정렬된 우선순위와 큐<pair>에 저장된 우선순위를 하나씩 비교하면서 정렬된 우선순위 보다 낮다면 뒤로 보내준다. 올바른 우선순위가 나오면 그 배열 번호를 결과 큐에 넣어준다. 결과 큐에 넣어주는 이유는 이후에 몇 번째로 프린트 되었는지 확인하기 위해서이다. 이렇게 반복해서 모든 문서를 결과 큐에 넣어 주었다면 결과 큐에서 하나씩 pop하여 카운트하면서 원하는 배열 번호가 나올때까지 반복해주면 문제는 해결된다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int main(){
 
    int t, n, m, temp;
    int cnt2;
    vector<int> ans;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        queue<pair<int, int>> q1;
        queue<int> result;
        vector<int> mx;
        cin >> n >> m;
        for (int j = 0; j < n;j++){
            cin >> temp;
            mx.push_back(temp); // 우선 순위만 저장
            q1.push(make_pair(j, temp)); // 우선 순위와 해당하는 배열 번호 저장
        }
 
        sort(mx.begin(), mx.end(), greater<int>());
 
        int cnt = 0;
        while (cnt < n){ // 모든걸 프린트 할 때 까지
            while (q1.front().second != mx[cnt]) // 꺼내야할 우선 순위보다 낮다면
            {
                q1.push(q1.front()); // 맨 뒤로 보냄
                q1.pop();
            }
            if(q1.front().second == mx[cnt]){ // 꺼내야할 프린트라면
                result.push(q1.front().first); // 결과 큐에 배열 번호를 넣어줌
                q1.pop();
                cnt++; // 다음 우선순위로 넘김
            }// 프린트 된 순서대로 저장하기 위해 결과 큐를 씀
        }
        cnt2 = 0; 
        while(!result.empty()){
            if(result.front() == m){ //원하는 배열 번호를 보면
                ans.push_back(cnt2); //프린트된 순서 저장.
                break;
            }
            else{
                result.pop(); // 하나씩 빼면서 원하는 배열 번호 확인
                cnt2++; //하나씩 카운트
            }
        }
    }
    for (int i = 0; i < ans.size();i++){
        cout << ans[i]+1 << '\n';
    }
    return 0;
}

사용 문법 queue, pair

 

yea!