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

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

구현, 자료구조, 시뮬레이션, 큐 문제. 우선순위 큐를 이용하면 쉽게 풀 수 있지만, 필자는 우선순위 큐를 이용하지 않고 단순 큐만 이용하여 문제를 풀었다. 우선순위 큐를 이용한 다른 분의 풀이도 함께 첨부하도록 하겠다.

1. 문제

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

[문제]

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

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

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

[입력]

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

[출력]

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

[예제 입력 1]

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

[예제 출력 1]

1
2
5

반응형

2. 풀이

/* 우선순위 큐를 이용하지 않은 풀이 */

풀이의 로직은 다음과 같다. 아래의 로직을 코드로 구현하였다.

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

 

/* 우선순위 큐를 이용한 풀이 */

우선순위 큐는 우선순위가 가장 높은 데이터부터 먼저 삭제하는 자료구조이다.

우선순위 큐는 배열, 연결리스트, 힙 등으로 구현이 가능한데, 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.

힙은 완전 이진 트리의 일종으로, 우선순위 큐를 구현하는 데 사용된다. 

이는 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있도록 만들어진 자료구조이다.
힙은 일종의 반정렬 상태 (느슨한 정렬 상태)를 유지한다.

다시 말해, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 큰 이진 트리를 유지한다. 

힙에서는 중복된 값을 허용한다.

최대 힙(max heap)
"부모 노드의 key 값 >= 자식 노드의 key 값"을 만족하는 완전 이진 트리

최소 힙(min heap)
"부모 노드의 key 값 =< 자식 노드의 key 값"을 만족하는 완전 이진 트리

이 문제에서는 중요도가 높은 문서일수록 가장 먼저 인쇄해야 하므로 최대 힙을 사용하면 된다!

3. 코드

/* 우선순위 큐를 이용하지 않은 풀이 */
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main(int argc, char* argv[]) {
	/* Faster */
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	/* Input */
	int T; cin >> T;
	for (int i = 0; i < T; i++) {
		/* Input */
		int N, M; cin >> N >> M;

		/* Init */
		int arr[10] = {};
		queue<pair<int, bool>> q;
		bool flag = false; //반복문 탈출을 위한 flag 변수

		for (int j = 0; j < N; j++) {
			int elem; cin >> elem;

			arr[elem]++;
			q.push(make_pair(elem, j == M));
		}

		/* Calculate */
		for (int j = 9; j >= 0; j--) {
			while (arr[j] > 0) {
				if (j == q.front().first) {
					if (q.front().second == true) {
						cout << N - q.size() + 1 << '\n';
						flag = true;
						break;
					}

					q.pop();
					arr[j]--;
				}
				else { // j != q.front().first
					q.push(q.front());
					q.pop();
				}
			}

			if (flag == true)
				break;
		}
	}

	/* End */
	return 0;
}

/*

//debug
for (int j = 0; j < 10; j++) {
	cout.width(3);
	cout << j << ' ';
}
cout << '\n';
for (int j = 0; j < 10; j++) {
	cout.width(3);
	cout << arr[j] << ' ';
}
cout << '\n';

while (!q.empty()) {
	cout.width(3);
	cout << q.front().first << '&' << q.front().second << ' ';
	q.pop();
}
cout << '\n';

*/

/* 우선순위 큐를 이용한 풀이 */
#include<iostream>
#include<queue>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

	while(t--){
        int n, m;
        cin >> n >> m;
        
        // 인덱스가 m인 문서가 몇번째로 인쇄되었는지 카운팅하는 변수
        int cnt = 0;

        queue<pair<int, int>> q;
        priority_queue<int> pq; // 기본적으로 최대 힙 

        for (int i = 0; i < n; i++){
			int x; 
			cin >> x; 
			
            q.push({ i, x }); // 인덱스와 중요도 
            pq.push(x); // 중요도가 높은 순으로 
        }

        while (!q.empty()){
            // 큐의 front 원소를 꺼내서
            int idx = q.front().first;
            int priority = q.front().second;
            q.pop();

            // 우선순위 큐의 top과 중요도가 일치하면
            if (pq.top() == priority){
                pq.pop();
                cnt++; // 문서 하나 인쇄할 때마다 증가

                // 현재 문서의 인덱스가 m인 경우
                if (idx == m){
                    // 몇번째로 인쇄되었는지 출력
                    cout << cnt << '\n'; 
                    break; // 그 다음 테스트 케이스로 넘어가기
                }
            }
            else { 
				// 중요도가 높지 않으면 큐의 rear에 다시 push
                q.push({ idx, priority });
            }
        }

        // 각 테스트 케이스마다 q, pq를 새로 생성하기 때문에 
        // 컨테이너 초기화는 필요하지 않다.  
    }

    return 0;
}