[백준] 1966 프린터 큐 with C++

문제설명

---

입출력 예제

---

개념

　문서의 개수와 중요도가 주어졌을 때, 큐에서 M번째에 해당하는 문서가 몇 번째로 출력되는지 묻는 문제다. 프린터 대기열은 큐 자료 구조를 사용한다는 점과, 문서의 중요도가 필요하다는 점에서 문서의 이름과 중요도를 자료형 pair로 받아 처리해야 한다는 점을 유의하자.

---

풀이

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

int main()
{
	int T, N, M, n;
	cin >> T;

　테스트 케이스의 수 T, 문서의 개수 N, 출력 순서가 궁금한 정수 M, 중요도 n을 초기화한다.

 

	while (T--)
	{
		int index = 0;
		cin >> N >> M;

		queue <pair<int, int>> q;
		pair<int, int> ans;

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

			if (i == M)
				ans = { n , i };
		}

　프린터 대기열 q와 출력 순서 index, 그리고 index에 해당하는 문서 ans를 초기화한 후, queue에 값을 삽입한다.

 

		while (!q.empty())
		{
			bool isTrue = false;
			pair<int, int> tmp = q.front();
			q.pop();

			for (int i = 0; i < q.size(); ++i)
			{
				pair<int, int> next = q.front();
				q.pop();

				if (tmp.first < next.first)
					isTrue = true;

				q.push(next);
			}

　큐에서 하나씩 꺼내서 우선순위가 맞도록 초기화한다.

 

			if (!isTrue)
			{
				index++;

				if (tmp.second == M)
				{
					cout << index << "\n";
					break;
				}
			}

			else
				q.push(tmp);
		}
	}
}

　반복이 끝나고 난 후, 큐의 맨 앞의 값과 index를 비교하며 일치하면 출력순서이므로 답을 출력한다.

 

총합본

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

int main()
{
	int T, N, M, n;
	cin >> T;

	while (T--)
	{
		int index = 0;
		cin >> N >> M;

		queue <pair<int, int>> q;
		pair<int, int> ans;

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

			if (i == M)
				ans = { n , i };
		}

		while (!q.empty())
		{
			bool isTrue = false;
			pair<int, int> tmp = q.front();
			q.pop();

			for (int i = 0; i < q.size(); ++i)
			{
				pair<int, int> next = q.front();
				q.pop();

				if (tmp.first < next.first)
					isTrue = true;

				q.push(next);
			}

			if (!isTrue)
			{
				index++;

				if (tmp.second == M)
				{
					cout << index << "\n";
					break;
				}
			}

			else
				q.push(tmp);
		}
	}
}