[백준 1966] 프린터 큐

문제

프린터는 다음과 같은 조건에 따라 인쇄된다.

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

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

프린터의 문서 수가 주어졌을 때 어떤 문서가 몇 번째로 출력되는지 구하라

 

입력

첫째 줄에 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에 문서의 수와 확인하고자 하는 문서의 위치를 입력하고 이어서 문서의 중요도를 입력한다.

 

출력

확인하고자 하는 문서가 몇 번째로 인쇄되는지 출력한다.

---

접근

문서들의 위치에 따른 중요도를 큐에 담는다. 그리고 중요도가 큰 것과 같으면 pop을 하고 그렇지 않다면 front에 있는 문서를 빼서 뒤로보낸다. 중요도가 같을 때가 몇 번인지 확인하도록 한다.

 

구현

각 테스트 케이스마다 문서의 수 확인하고자하는 문서의 위치를 입력받아 N, M에 저장한다.

그리고 문서의 중요도는 number에 저장하며 q에는 문서의 위치와 중요도를 쌍으로 저장한다.

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
q = deque()

 

문서의 수만큼 for문으로 탐색하여 문서의 위치와 그 위치에 해당되는 중요도를 함께 담는다.

이후 문서의 중요도를 오름차순으로 정렬한다.

    for idx in range(N):
        q.append((idx, numbers[idx]))
    numbers = sorted(numbers)

 

while문을 통해 조건에 부합하기 전까지 계속 반복한다. 

먼저 큐의 가장 앞에있는 중요도가 인쇄되어야하는 가장 높은 중요도라면 최종해를 증가시킨다.

그리고 해당 문서가 확인하고자하는 문서라면 while문을 종료한다. 그렇지 않다면 중요도가 오름차순으로 담긴 numbers의 맨 뒤(중요도가 가장 큰) 문서를 제거하고 큐에서는 앞의 원소를 제거한다. 

하지만 현재 문서가 인쇄되어야 하는 문서가 아니라면 계속 뺏다가 뒤로 다시 넣는 작업을 한다. 이 작업은 최종해를 증가시키지 않는다.

    while True:
        if numbers[-1] == q[0][1]:
            answer += 1
            if q[0][0] == M:
                break
            numbers.pop()
            q.popleft()
            continue
        a, b = q.popleft()
        q.append((a, b))

---

전체 코드

from _collections import deque
test_case = int(input())
for tc in range(test_case):
    N, M = map(int, input().split())
    numbers = list(map(int, input().split()))
    q = deque()
    for idx in range(N):
        q.append((idx, numbers[idx]))
    numbers = sorted(numbers)

    answer = 0
    while True:
        if numbers[-1] == q[0][1]:
            answer += 1
            if q[0][0] == M:
                break
            numbers.pop()
            q.popleft()
            continue
        a, b = q.popleft()
        q.append((a, b))
    print(answer)