프린터 큐

Printer Queue

---

◎ Problem Definition

1966번: 프린터 큐

---

◎ Implementation

1. Problem Type 

 - 자료구조/Queue (Silver 3)

2. Problem Analysis

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.

▶ 중요도와 Queue의 index 정보가 동시에 필요하기 때문에 tuple 혹은 dict 형태의 자료형을 적용해보았습니다. 

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

▶ FIFO의 출력 데이터의 우선순위가 낮으면 다시 Queue에 입력되어야합니다. 이러한 구조는 일반적인 우선순위큐와는 다른 로직입니다. 따라서, OrderedDict 을 사용하여 구현해보았습니다. 

3. Solution_1 (☆초기 접근)

▶ 완성 코드 (python)

# backjoon : #1966, Printer Queue
# date     : 25th, June. 2022
# writer   : Lemonsoda
# reference: https://www.acmicpc.net/status?user_id=elie&problem_id=1966&from_mine=1

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

from collections import OrderedDict


def get_order(n, priority):
    '''
    # n : 몇 번째로 인쇄되었는지 궁금한 문서의 Queue에서의 위치 (0 <= n < N)
    # priority : N개의 문서의 중요도 {index : priority}
    '''
    cnt = 1 
    maximum = max(priority.values())
    data = priority.popitem(last = False) # 0번째 아이템 pop
    while data[0] != n or data[1] != maximum: 
        if data[1] == maximum :
            cnt += 1
            maximum = max(priority.values())
        else:
            priority[data[0]] = data[1] 
        data = priority.popitem(last = False) 
    return cnt


n_test = int(input()) # 쳣 줄은 테스트 케이스의 수
for i in range(n_test):
    dict = OrderedDict()
    N, pos = map(int, input().split()) 
    data = list(map(int, input().split()))
    for i in range(len(data)):
        dict[i] = data[i] 
    ans = get_order(pos, dict)
    print(ans)

▶ 성능 

4. Solution_2 (☆공개된 다른 코드 참조)

이번에는 C/C++로 구현된 백준 1966 프린터 큐 [C++] :: 건호의 코딩공부 (tistory.com) 을 클론코딩하며 학습해보았습니다. C/C++에서는 STL의 queue와 priority_queue를 동시에 적용했습니다. queue를 사용하여 Queue의 first input 값을 하나씩 비교하고 최대값이 아니면 다시 queue에 push하는 부분은 동일했습니다. 다만, queue의 우선순위 최대값을 따로 구하지 않고, priority_queue를 입력하여 하나씩 출력되는 값과 비교한 코드였습니다. priority queue를 적용하는 간편한 방법이었습니다. 

▶ 완성 코드 (C/C++)

// Reference : https://numerok.tistory.com/134

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	int count = 0;
	int test_case;
	cin >> test_case;
	int n, id, priority; // 문서 개수, target 문서 번호, 중요도
	for (int i = 0; i < test_case; i++) {
		count = 0;
		cin >> n >> id;
		queue<pair<int, int>> q;
		priority_queue<int> prior_q; // 우선순위 큐
		for (int j = 0; j < n; ++j) {
			cin >> priority;
			q.push({ j, priority });
			prior_q.push(priority);
		}

		while (!q.empty())
		{
			int index = q.front().first;
			int value = q.front().second;
			q.pop();
			if (prior_q.top() == value) {
				prior_q.pop();
				++count;
				if (index == id) {
					cout << count << endl;
					break;
				}
			}
			else {
				q.push({ index, value });
			}
		}
	}
}

▶ 성능

 

 

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

 

 

---

◎ Results

- Queue를 직접 활용하여 문제의 내용을 구현하면 손쉽게 해결할 수 있는 문제였습니다. 또, maximum 값을 별도로 계산할 수도 있지만, priority Queue를 하나 더 적용하여 출력값을 비교하는 방법을 적용할 수도 있음을 알게되었습니다. 

- 단연코 C/C++ 코드의 수행시간이나 메모리 사용 측면에서 훨씬 효율적이었습니다. HW에 실장되는 코드는 C/C++이 파이썬보다는 효과적 자원 사용을 보장해준다는 생각이 들었고, C/C++ 공부도 꾸준히 함께 해야겠다고 생각했습니다.