백준 1966 - 프린터 큐

아래 조건에 따라 인쇄를 하는 프린터에서 임의의 순서로 넣은 문서가 몇번째로 출력되는지 구하는 문제입니다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

이 문제를 해결할 수 있는 방법은 정말 많지만 deque를 이용해 해결했습니다. deque를 이용해 위 프린터 작동 방식을 직관적으로 구현할 수 있습니다.

중요도 높은게 있다면 가장 앞의 문서를 뒤에 push하고 front에서 pop을 진행하면 작동 구조가 그대로 구현됩니다.

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

int main()
{
	int cnt;
	std::cin >> cnt;

	for (int i = 0; i < cnt; i++)
	{
		int docsCnt, num;
		std::cin >> docsCnt >> num;

		std::deque<int*> printerDeque;

		int* target = nullptr;
		for (int j = 0; j < docsCnt; j++) // O(N)
		{
			int* tmp = new int;
			std::cin >> *tmp;
			printerDeque.push_back(tmp);
			if (j == num) target = tmp;
		}

		int size = printerDeque.size();
		for(int j = 0; j < size; j++) // O(N) worst가 2N
		{
			int cur = *printerDeque.front();

			auto f = std::find_if(printerDeque.begin(), printerDeque.end(), [cur](int* a) { return cur < *a; }); // O(N)
			if (f != printerDeque.end())
			{
				printerDeque.push_back(printerDeque.front());
				printerDeque.pop_front();
				j--;
			}
			else
			{
				if (printerDeque[0] == target)
				{
					std::cout << j + 1 << std::endl;
					break;
				}
				printerDeque.pop_front();
			}
		}
	}
}

단점은 Time complexity가 $O(N^2)$이기에 빠른 코드라고는 볼 수 없습니다.

다른 분들이 푸신 코드 중 priority_queue를 이용해 푼 분들의 코드가 해당 코드보다는 빠르나, 대부분 priority_queue 외에도 queue와 pair을 별도로 할당해 사용하기에 Space complexty 관점에서는 위 코드가 더 효율적입니다.

다른 분들의 코드는 아래 링크들을 참고했습니다.
https://numerok.tistory.com/134

https://kokodakadokok.tistory.com/entry/%EB%B0%B1%EC%A4%80-1966%EB%B2%88-%ED%94%84%EB%A6%B0%ED%84%B0-%ED%81%90-C-%ED%92%80%EC%9D%B4

https://artiper.tistory.com/72

https://lumir.tistory.com/62