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

1966번: 프린터 큐

우선순위 큐까지는 사용할 생각을 했는데, pair를 사용해 값과 인덱스를 담는 것을 생각못해서 시간이 많이 걸린 아쉬운 문제였다.

 

중요 포인트 요약

 

문제

1. Queue의 가장 앞에 있는 문서의 '중요도'를 확인
2. Queue다른 곳에 하나라도 '중요도'가 더 높은 것이 있다면 현재 가장 앞에 있는 문서를 Queue의 맨뒤로 보낸다.
3. 가장 앞에 있는 문서의 '중요도'가 가장 높으면 바로 출력.

입력

1. 총 테스트 케이스의 개수
2. 테스트 케이스 첫째줄
   2.1 문서의 개수 
   2.2 언제 출력될지 궁금한 문서가 현재Queue에 있는 위치.
3. 테스트 케이스 둘째줄
   각 문서의 중요도

출력

 2.2에서 말한 Queue에 있는 문서가 몇 번쨰로 인쇄되는지 출력.

 

풀이

 지정한 문서가 언제 출력되는지 알고 싶기에, 문서의 중요도와 인덱스를 둘다 가지고 있어야 문서가 계속 이동해도 찾을 수 있을 것이다. 

 그래서 큐는 총 2개가 필요한데, 인덱스와 값을 가지고 있는 Queue하나(페어큐라고 하겠습니다.)와 숫자가 내림차순으로 정렬되어 있는 Queue가 하나 필요하다. 굳이 큐를 정렬할 필요 없이, 우선순위 큐를 사용하여 값을 정렬된 값으로 만들게 한다.

 

문제 입력 예제에 있는 것으로 예시를 들어보겠다.

6 0 

1 1 9 1 1 1

1. 1은 Queue 내부에 더 큰 9가 있기에 pop후 push되어 맨 뒤로 붙는다.
2. 이 행위를 반복하다 페어큐의 값과 우선순위 큐의 값과 일치하면 우선순위 큐는 pop된다. (우선 먼저 9가 pop이 될 것이다.)
   +@ (우선순위 큐에 있는 값이 pop되어야 다른 1값들을 pop시킬 수 있다.)
3. pq가 pop이 될 때 count를 증가시킨다.
4. 1~3을 계속 반복하다가 location과 m이 같고, 중요도의 값이 같은 상황이 나오면 출력을 하고 break시킨다.

 

+@ pari에 관한 설명.

큐에는 우선순위값과 위치를 같이 넣어야 하기 때문에 pair라는 것을 사용하는데, 

queue<pair<int, int>> q;

이와 같이 선언하고 큐에 예제 데이터 1 1 9를 넣을 때

q.push({ j, importance }); //j는 인덱스 값, importance는 우선순위값

위 처럼 코드를 작성하면 다음과 같은 표가 나온다.

이런 상태에서 pop과 push를 하게 되면

위와 같은 결과가 된다. 즉, 우선순위값과 제일 처음 데이터가 들어왔던 순서도 같이 움직이게 된다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

int main()
{
	int testn;
	int n, m;
	int importance;
	int count;

	scanf("%d", &testn);

	for (int i = 0; i < testn; i++) {
		count = 0;
		scanf("%d %d", &n, &m);
		
		priority_queue<int> pq; // 내림차순 정렬해야 pop할 때 높은게 빠져나옴.
		queue<pair<int, int>> q;

		for (int j = 0; j < n; j++) {
			scanf("%d", &importance);
			q.push({ j, importance });
			pq.push(importance);
		}

		while (!q.empty()) {
			// 위치값과, 우선순위 값을 가져온 뒤 pop수행
			int location = q.front().first;
			int value = q.front().second;
			q.pop();
            
			// 값 비교
			if (pq.top() == value) {
				pq.pop();
				++count;
				if (m == location) {
					printf("%d\n", count);
					break;
				}
			}

			else q.push({ location, value });
		}
	}

	return 0;
}