백준 1966 프린터 큐(brute force)

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

1966번: 프린터 큐

#include <iostream>
#include <queue>

using namespace std;
int N, M;

int cnt;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int num;
    cin >> num;
    while (num--)
    {
        queue<pair<int, int>> q; //중요도, index
        priority_queue<int> pq;
        cin >> N >> M;
        for (int i = 0; i < N; i++)
        {
            int tmp;
            cin >> tmp;
            q.push(make_pair(tmp, i));
            pq.push(tmp);
        }
        while (!q.empty())
        {
            int priority = q.front().first;
            int index = q.front().second;
            q.pop();
            if (pq.top() == priority)
            {
                pq.pop();
                cnt++;
                if (index == M)
                {
                    cout << cnt << "\n";
                    cnt = 0;
                    break;
                }
            }
            else
            {
                q.push(make_pair(priority, index));
            }
        }
    }
}

 

queue와 priority queue를 같이 사용하면 쉽게 풀 수 있는 문제였다.

 

queue, priority queue, 그리고 이 문제에 대한 정보는

 

https://en.cppreference.com/w/cpp/container/queue

https://en.cppreference.com/w/cpp/container/priority_queue

http://melonicedlatte.com/algorithm/2018/02/18/230705.html

 

이곳들에서 참조했다. 

 

짚고 넘어가야할 가장 중요한 점은 queue에서 front가 priority queue에서는 top이 된다는 것이 었다. 또한 stack이나 queue에는 clear 기능이 존재하지 않는데 이 때문에 stack 혹은 queue를 비울 때는 while(!q.empty()) q.pop() 과 같은 연산으로 초기화 시켜주어야 한다.