프린터 큐(1966)

들어가는 말

간단하게 말하자면, n번째 우선순위에 있는 일이 몇 번째에 실행되느냐에 대한 문제다. 우선순위 큐를 사용하면 더욱 쉽게 접근할 수 있다. index가 필요한데, 문제는 큐에서는 인덱스를 지원하지 않는다는 점이다. 이는 카카오 코딩 테스트에서 배운 pair의 방식을 사용하면 될 것이다. 아쉽게도 내 힘으로 전체를 풀어내지는 못했다. 다른 사람들의 풀이를 참고하지 않고 슥슥 풀어내는 날이 금방 왔으면 좋겠다...

코드 설명

1. 큐 헤더 파일을 추가한다. 우선순위 큐는 priority_queue<자료형>이렇게 써주면 된다.
2. 몇 번 반복할 건지 변수 num을 받은 후에 num대로 반복해준다.
3. num 반복문 안에서 input이 총 몇 개 있고(n) 몇 번째 input인지(m)를 입력받는다.
4. 큐는 총 두 개를 만들어 주는데, 우선선위를 확인할 큐(priority_queue)와 값과 인덱스를 확인할 큐(pair을 이용)을 정의해준다.
5. 큐에 들어갈 값을 받는데, pair에서는 몇 번째 인덱스인지 j도 함께 저장해 준다.
6. 마지막 반복문으로 k번째 값이 몇 번째에 나오는지를 계산해준다. f에다가는 인덱스를, s에다가는 값을 넣어준다. 그리고 만일 s의 값이 우선순위가 제일 높은 값이라면 ppq(priority queue)를 pop해준 다음 count를 계산해 준다. 이때 인덱스가 우리가 찾는 값이라면 출력을 해준 뒤 break로 while문을 탈출한다. 만일 s가 우선순위가 높은 값이 아니라면 다시 pq에 넣어준다.

코드

#include<queue>
#include<iostream>
using namespace std;

int main() {
	int num;
	cin >> num;

	for (int i = 0; i < num; i++) {
		int n, m;
		cin >> n >> m;

		queue<pair<int, int>> pq;
		priority_queue<int> ppq;

		for (int j = 0; j < n; j++) {
			int input;
			cin >> input;
			pq.push(make_pair(j, input));
			ppq.push(input);
		}

		int count = 0;
		while (!pq.empty()) {
			int f = pq.front().first;
			int s = pq.front().second;

			pq.pop();

			if (s == ppq.top()) {
				ppq.pop();
				count++;

				if (f == m) {
					cout << count << endl;
					break;
				}
			}
			else {
				pq.push(make_pair(f, s));
			}
		}
		count = 0;
	}
}