[Python] 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 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

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

---

풀이

• 큐와 우선순위 큐의 개념에 대해 알고 있다면 쉽게 풀 수 있는 문제다.

• 다양한 방법이 있겠지만 가볍게 collections에 있는 deque모듈을 활용해 풀었다.

• 방법과 코드를 보면 알겠지만 효율성보다 직관적으로 코드를 구현해 풀었기에 효율적이지 않을 수 있다. 효율성을 따진다면 다른 풀이를 확인하도록 하자.

• 우선순위를 확인하는 큐를 구현하고 그 뒤에 몇번째 종이인지 확인하는 로직을 추가했다.

순서

1. 먼저 큐를 앞에서부터 꺼내 find_priority함수를 이용해 뒤에 더 큰 우선순위가 있는지 확인한다.
   1. 더 큰 우선수위가 있다면 popleft로 앞에 종이를 빼고 append로 맨 뒤에 넣어준다.
   2. 없다면 바로 출력이 가능하므로 popleft를 통해 제거한다.

2. 여기에 인자 M을 통해 몇번째 종이인지 확인하는 로직을 추가한다.
   1. 앞에 종이가 빠져나가거나 뒤로가면 순서가 줄어드는 것이므로 M -= 1을 해준다.
   2. M이 0이되면 해당 종이의 우선순위를 점검할 차례라는 뜻이다.
   3. 만약 우선순위에서 밀려 뒤로 가게되면 밀린 순서 (len(q)-1)만큼 더해주도록 한다.

답

from sys import stdin
from collections import deque

input = stdin.readline


# 우선순위 확인
def find_priority(q):
    for p in q:
        if q[0] < p:
            return False
    return True


# 메인 함수
def print_queue(q, m):
    idx = 1
    while q:
        if find_priority(q):
            if m == 0: # 점검하고자 하는 종이가 나가는 경우
                break
            else: # 다른 종이가 빠져나갈 경우
                m -= 1
            q.popleft()
            idx += 1
        else:
            if m == 0: # 점검하고자 하는 종이가 뒤로 밀릴 경우
                m += len(q) - 1
            else: # 다른 종이가 밀릴 경우
                m -= 1
            paper = q.popleft()
            q.append(paper)
    return idx


# 입력 및 출력
if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N, M = map(int, input().split())
        queue = deque(map(int, input().split()))
        res = print_queue(queue, M)
        print(res)

Uploaded by Notion2Tistory v1.1.0