[c/c++] 백준 1966(Silver 3)

🔨 문제

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

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

🔨 해결방법

priority_queue를 사용하여 풀었다. 이번 문제를 풀면서 priority_queue에 대해서 처음 알게 되었는데 매우 유용한 것 같다!
https://m.blog.naver.com/kks227/220791188929

priority_queue는 우선순위 큐를 나타내는 C++ STL의 컨테이너 어댑터이다. 보통 queue에서는 pop을 하면 제일 먼저 들어왔던 원소가 추출되는데, priority_queue에서는 우선순위가 높은 순서에 따라 추출된다.

우선순위 큐는 보통 힙(heap)이라는 자료구조로 구현되는데 보통은 동의어로 사용되고 top이 최댓값인 우선순위 큐를 최대 힙, 최솟값인 우선순위 큐를 최소 힙이라고 부르기도 한다. 또한 원소들을 다 넣고 pop을 하면 정렬된 순서로 원소들이 빠져나오게 되는데 이렇게 정렬하는 것을 힙 소트(heqp sort)라고 한다.

그리고 나의 풀이 방법은 큐와 우선 순위 큐를 비교하여 찾고자하는 타겟이 나올때까지 cnt를 증가시키고 그 값을 출력하는 방식으로 구현하였다.

🔨 코드

#include <iostream>
#include <queue>
using namespace std;


int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t=0, n=0, target=0, num=0;  // 테케, 문서의 개수, 타겟 문서, 중요도
    cin >> t;
    for(int i=0; i < t; i++){
        cin >> n >> target;
        queue <pair<int,int>> q;
        priority_queue <int> pq;
        for(int j=0;j<n;j++){
            cin>> num;
            q.push(make_pair(j,num));
            pq.push(num);
        }
        int cnt=0;
        while(!q.empty()){
            int index = q.front().first;
            int priority = q.front().second;

            if(pq.top() > priority){
                q.push(make_pair(index, priority));
                q.pop();
            }
            else {
                cnt++;
                q.pop();
                pq.pop();
                if(index == target){
                    cout << cnt << '\n';
                    break;
                }
            }
        }
    }

    return 0;
}