BOJ : 1966 프린터 큐

---

[BOJ 1966(S3) 리뷰]

시뮬레이션 문제다. 설명에 나온대로 프린터 큐가 존재하고 큐에 있는 각각의 작업마다 중요도가 있다. 큐의 맨앞 작업부터 하나씩 내보내야 하는데 만약 뒤에서 기다리고 있는 작업 중 현재의 작업보다 중요도가 높은 작업이 있다면 현재의 작업을 맨 뒤로 보내고 중요도가 높은 작업먼저 수행해야 한다. 이 때 M번 작업이 몇번만에 수행이되는지를 출력해야 한다.

 

가장 먼저 떠올렸던 구현은 큐가 빌때까지 반복문을 돌며 계속해서 뒤에있는 큐중 중요도가 있는작업이 있는지 확인하고 있다면 현재 큐를 뒤로 보내는 작업이다. 이 작업은 시간복잡도 O(n^2)에 수행된다.

N이 100이하이므로 이 코드도 충분히 통과가 가능하지만, 나는 O(n)에 구현하기 위하여 우선순위큐를 이용했다.

우선순위큐를 이용해 중요도를 내림차순으로 정렬한 후에 큐를 돌면서 현재 작업이 우선순위큐의 top보다 낮다면 (더 높은 중요도가 존재한다는 것) 현재 작업을 뒤로밀고, 만약 현재 작업이 우선순위큐의 top과 같은값이라면 해당 작업을 pop후에 cnt를 증가시키면된다. 만약 현재 pop을 하려는 작업의 index가 M이라면 cnt값을 출력하고 종료하면 된다.

 

 

---

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int tc;
	cin >> tc;
	while (tc--)
	{
		int N, M;
		cin >> N >> M;
		queue <pair<int,int>> printer;
		priority_queue <int,vector<int>,less<int>> important;

		for (int i = 0; i < N; i++)
		{
			int val;
			cin >> val;
			important.push(val);
			printer.push({ i,val });
		}

		int cnt = 0;
		while (!important.empty())
		{
			int top = important.top();
			if (printer.front().second != top)
			{
				auto temp = printer.front();
				printer.push({ temp.first,temp.second });
				printer.pop();
			}
			else
			{
				cnt++;
				if (printer.front().first == M)
				{
					cout << cnt<<'\n';
					break;
				}
				printer.pop();
				important.pop();	
			}
		}
	}
	


}