[백준 1966] 프린터 큐 (C++)

풀이

처음에 시간 초과가 난 문제.

이유는 현재 가장 높은 중요도 문서를 찾는데 O(N)를 추가로 구하기 때문이다.

생각해보니까. 우선순위 큐를 이용하면 O(N)에 찾는 것이 아닌 가장 위에 있는 원소만 확인해보면

O(1)에 된다는 것을 알았다.

 

기본적으로 우선순위 큐는 삽입할 때 알아서 우선순위대로 만들어주기 때문이다.

 

자료구조 2개를 써서 풀었다.

- 큐에는 (중요도, 문서 번호)

- 우선순위 큐에는 (중요도)

 

문서를 하나씩 앞에서 보면서 현재의 문서보다 더 높은 중요도 문서가 있으면

해당 문서를 큐 뒤에 보낸다.

 

아니라면 현재의 문서를 큐에서 pop 하고, 우선순위 큐에서도 pop 한다.

이때 내가 찾는 문서의 번호라면 그 값을 출력하면 된다.

 

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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--)
	{
		queue<pair<int, int>> q; // (priority, num)
		priority_queue<int> pq;  // priority
		int n, m;

		cin >> n >> m;
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			q.push({ x, i }); 
			pq.push(x);
		}

		int cnt = 0;
		while (!q.empty())
		{
			int now = q.front().first;
			int num = q.front().second;

			if (!pq.empty() && now < pq.top())
			{
				q.push(q.front());
				q.pop();
				continue;
			}

			cnt++;
			pq.pop();
			q.pop();
			if (m == num)
			{
				cout << cnt << '\n';
				break;
			}
		}
	}
	return 0;
}