백준 1966: 프린터 큐

문제 요약

현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다.

문제 분류

• 구현
• 자료 구조
• 시뮬레이션
• 큐

문제 풀이

문제에서 말하는대로 구현하면 된다. 이 해법이 나오기까지 몇 가지 안 사항이 있는데

1. 큐는 int가 아닌, pair<int,int>로 삽입된 순서를 같이 삽입하는 편이 좋다, q.push({i, in});

2. 배열 등으로 우선순위를 저장해서 큐의 뒤에 우선순위가 더 큰게 있는지 파악해야 한다.
   이 부분은 우선순위 큐로 구현한 사람도 있고 여러가지 풀이가 존재했다.

3. C++ STL의 큐를 비우고 싶을때는 생성자로 재할당 하면 된다.

4. 때에 따라 memset()보다는 fill_n()이 더 빠르다.

배열을 초기화 하고 싶어서 memset()을 썼더니 시간초과, std::fill_n()을 썼더니 적어도 시간초과는 나오지 않았다.

결국 큐에 순차적으로 삽입한 뒤
큐의 앞보다 큰 값이 뒤에 있는 경우에는 뒤로 삽입하고
그렇지 않은 경우(가장 앞이 가장 큰 값인 경우) 가장 앞의 원소를 큐에서 삭제하고 카운트를 1증가시킨다. 이 때, 삭제된 원소의 인덱스 번호가 입력된 m과 같을 경우 break하고 카운트값을 출력한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
	int t, n, m, in, cnt, max;
	queue<pair<int, int>> q;
	int ary[10] = { 0, };
	scanf("%d", &t);

	while (t--) {
		fill_n(ary, 10, 0);
		scanf("%d%d", &n, &m);
		cnt = 0;
		max = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d", &in);
			q.push({ i, in });
			ary[in]++;
			if (in > max) max = in;
		}
		while (!q.empty()) {
			if (q.front().second == max) {
				ary[max]--;
				while (ary[max] <= 0) max--;
				cnt++;
				if (q.front().first == m) break;
			}
			else q.push({ q.front().first, q.front().second });
			q.pop();
		}
		printf("%d\n", cnt);
		q = queue<pair<int, int>>();
	}
	return 0;
}