백준 1966번 - 프린터 큐 [Python]

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

1966번: 프린터 큐

 

안녕하세요! 오늘은 백준 1966번 프린터 큐 문제를 Python으로 풀이하는 방법에 대해서 정리해보려고 합니다. 이 문제는 큐 자료구조를 이용해 해결할 수 있는 문제입니다.

문제 이해

문제는 프린터의 출력 순서를 결정하는 알고리즘에 관한 것입니다. 문서의 중요도에 따라 출력 순서가 결정되며, 더 중요한 문서가 입력되면 앞서 대기하던 문서는 뒤로 밀리게 됩니다. 우리가 알아낼 것은 특정 문서가 언제 출력되는지를 알아내는 것입니다.

문제 접근 방식

큐를 이용해 문서의 순서를 관리하면서, 문서의 중요도에 따라 출력 순서를 변경하는 방식으로 문제를 접근합니다. 문서의 중요도를 체크하기 위해 파이썬의 내장 함수인 max()를 사용합니다.

코드 작성

아래는 이 문제에 대한 파이썬 풀이 코드입니다:

from collections import deque

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    queue = deque(map(int, input().split()))
    queue = deque([(i, idx) for idx, i in enumerate(queue)])

    count = 0
    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            count += 1
            if queue[0][1] == M:
                print(count)
                break
            else:
                queue.popleft()
        else:
            queue.append(queue.popleft())

코드 해설

먼저 테스트 케이스의 개수 T를 입력 받습니다. 각각의 테스트 케이스에 대해 문서의 수 N과 출력 순서를 알고 싶은 문서의 현재 위치 M를 입력받습니다. 그리고 문서들의 중요도를 입력받아 큐에 저장하되, 중요도와 함께 해당 문서의 초기 위치도 함께 저장합니다.

그 다음으로는 큐의 맨 앞 문서가 현재 가장 중요한 문서인지를 확인합니다. 만약 가장 중요한 문서라면 출력 카운트를 1 증가시키고, 그 문서가 우리가 찾고자 하는 문서인지 확인합니다. 만약 찾는 문서라면 그 때의 카운트를 출력하고 반복문을 종료합니다. 만약 찾는 문서가 아니라면, 그 문서는 출력되었으므로 큐에서 제거합니다.

 

만약 맨 앞의 문서가 가장 중요한 문서가 아니라면, 그 문서는 큐의 맨 뒤로 이동합니다.

이런 과정을 반복하면, 결국에는 모든 문서가 그 중요도에 따라 출력되게 되며, 우리는 원하는 문서가 몇 번째로 출력되는지 알 수 있습니다.

 

마치며

이 문제는 파이썬의 큐 자료구조를 이용하여 해결할 수 있었습니다. 문서의 중요도에 따라 순서가 바뀌는 프린터 큐의 동작을 잘 이해하고 이를 코드로 옮기는 것이 중요했습니다. 문제를 풀면서 큐의 기본적인 동작 방식에 대해서도 알게 되었습니다.

다음에 뵙겠습니다. Happy Coding!