[백준] 1966번: 프린터 큐 [C++]

 

알고리즘 분류: 구현, 자료 구조, 시뮬레이션, 큐

문제 링크: https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

 

 

【 풀이 】

 

주어진 테스트 케이스에서 특정 문서의 중요도가 몇 번째로 큰지 구하는 문제이다.

이 문제는 큐와 우선순위 큐, 그리고 pair를 사용하여 쉽게 해결할 수 있다.

다음은 이 문제의 단계적 접근방법이다.

 

1. pair에 각각 { 인덱스, 중요도 } 순으로 큐에 저장
2. 우선순위 큐를 구현하여 큐의 첫값과 우선순위 큐의 첫값을 비교
3. 큐 원소의 두번째값인 중요도가 일치하면 횟수를 카운트하고 pop
4. 인덱스번호까지 맞다면 횟수를 출력하고 반복문 탈출

 

 

 

【 코드 】

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

int main(void)
{
	int t;
	int n, m, num;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		int cnt = 0;
		queue<pair<int, int>>q;
		priority_queue<int>printer;
		cin >> n >> m;
		for (int j = 0; j < n; j++)
		{
			cin >> num;
			q.push({ j, num });		//	j는 문서 인덱스, num은 중요도
			printer.push(num);		//	중요도를 담는 우선순위 큐
		}
		while (!printer.empty())
		{
			int idx = q.front().first;		//	각 값을 새로운 변수에 저장
			int prior = q.front().second;		//	빈 큐에 접근하는 오류를 피하기 위함임
			q.pop();
			if (printer.top() == prior)		//	중요도가 가장 높은 경우
			{
				cnt++;
				printer.pop();
				if (idx == m)		//	찾고자 하는 문서일 경우
				{
					cout << cnt << '\n';
					break;
				}
			}
			else		//	중요도가 높은 문서가 남아있는 경우
				q.push({idx,prior});
		}
	}
	return 0;
}