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

1966번: 프린터 큐

이 문제를 푸는데 조금 오랜 시간이 걸렸다.

왜냐하면 문제의 설명이 다소 이해하기 어려웠기 떄문이다.

처음에 풀었던 방식은 큐 배열을 이용해서 중요도에 따라 다른 큐에 순차적으로 집어넣는 방식으로 했지만,

{1, 1, 9, 1, 1, 1}의 경우 0번 인덱스가 3번 인덱스보다 늦게 나와야 하므로 위의 방법은 틀리다.

그래서 리스트를 이용하여 맨 앞 인덱스의 중요도 보다 높은 인덱스가 있는지 스캔하며

있으면 push_back, pop_front를 이용해 문제에 주어진 작동방식대로 구현했다.

goto 문을 유용하게 이용한 것 같다.

#include <cstdio>
#include <list>

using namespace std;

int main()
{
	int T;
	scanf("%d", &T);
	while (T--) {
		int N, M;
		scanf("%d %d", &N, &M);
		list<pair<int, int>> papers;
		for (int i = 0; i < N; i++) {
			int importance;
			scanf("%d", &importance);
			papers.push_back(make_pair(i, importance));
		}
		int order = 1;
		while (true) {
			for (auto iter = papers.begin(); iter != papers.end(); ++iter) {
				if ((*iter).second > papers.front().second) {
					papers.push_back(papers.front());
					papers.pop_front();
					goto NEXT;
				}
			}
			if (papers.front().first == M) {
				printf("%d\n", order);
				break;
			}
			papers.pop_front();
			order++;
		NEXT:;
		}
	}
	return 0;
}

pair를 리스트의 요소 타입으로 지정하여 first에는 처음 인덱스, second에는 중요도를 넣었다.

이렇게 지정함으로써 출력하고자 하는 문서를 특정할 수 있다.

 

PS. 나중에 보니 리스트 보다는 덱을 쓰는 편이 더 낫지 않았을까 싶다.