[Baekjoon] 1966번: 프린터 큐

 

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

1966번: 프린터 큐

 

---

 

문제 해결 과정

착안

얼핏 보았을 때 우선순위 큐와 같은 동작인 것처럼 보이나, 현재 문서의 우선순위보다 우선순위가 높은 문서가 큐에 하나라도 있는 경우 현재 문서를 큐의 가장 뒤쪽으로 보내는 작업 때문에 std::priority_queue<> 클래스를 사용해봤자 해결에 별 도움이 되지 않을 것이라 판단하였다.

 

본래 큐 클래스는 Front의 값에 대해서만 확인 가능하고 큐의 중간에 있는 요소들은 접근할 수 없다. 그런데 문제에서 우선순위가 높은 문서가 있는지 확인하는 것을 요구하므로 우선순위 값만 추가적으로 별도의 std::vector<> 클래스에 저장하고 정렬하여 출력 순서를 따지는 목적으로 활용하고자 하였다.

* 더 똑똑한 방법이 있을 수도 있겠지만, 편의상 이렇게 구현해보고자 하였음.

 

구현

Priorities 배열(std::vector<int>)을 오름차순으로 정렬하고, 하나씩 우선순위 값을 pop_back() 하여 큐에서 꺼낸 데이터의 우선순위가 해당 값과 같으면 출력 순서를 증가, 아니라면 큐에서 꺼낸 데이터를 다시 큐에 push() 하도록 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct Data
{
	int Index;
	int Priority;
};

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

	while (T--)
	{
		cin >> N >> M;

		queue<Data> Queue;
		vector<int> Priorities(N);
		for (int i = 0; i < N; i++)
		{
			int priority;
			cin >> priority;
			Priorities.push_back(priority);
			Queue.push(Data{ i, priority });
		}

		sort(Priorities.begin(), Priorities.end());

		int order = 0;
		while (!Queue.empty())
		{
			Data data = Queue.front();
			Queue.pop();

			int priority = Priorities.back();
			if (data.Priority < priority)
				Queue.push(data);
			else
			{
				order++;
				Priorities.pop_back();

				if (data.Index == M)
				{
					cout << order << "\n";;
					break;
				}
			}
		}
	}
	
	return 0;
}

 

실행 결과