백준 1966번 프린터 큐 - Python

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 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

 

위 문제에서는 문제의 핵심은 내가 지정한 위치에 해당하는 값이 언제 출력되는가 입니다!

 

위 입출력 예제를 통해서 알고리즘이 어떻게 돌아가는지를 파악하는 것이 중요했습니다.

첫번째 줄에 3은 몇번 연산을 할 것인지 미리 알려주는 것 입니다. 즉 출력되는 값의 갯수라고 보셔도 됩니다

1번째 입력부터 보겠습니다. 1개의 문서가 들어가며 0번째(인덱스)의 문서가 출력되는 순서를 알려달라는 것이며

5는 문서의 우선순위입니다.

[5]

현재 문서가 1개 밖에 없기 때문에 1이 출력됩니다

 

2번째 입력을 보겠습니다. 4개의 문서가 들어가며 2번째(인덱스)의 문서가 출력되는 순서를 알려달라는 것입니다

문서들의 우선순위는 1,2,3,4 입니다. 2번째 인덱스에 있는 3은 언제 출력되는 가 입니다. 위 문제에서 우선순위가 높은 것이 먼저 빠져나가야 하기 때문에 우선순위가 나보다 높거나, 같을지라도 나보다 앞에 있으면 먼저 출력됩니다

연산 순서는 이렇게 됩니다.  [1,2,3,4] -> [2,3,4,1] [2,3,4,1] -> [3,4,1,2][3,4,1,2] -> [4,1,2,3] 

* count 1번째 였던 4가 프린터에서 출력

[4,1,2,3] -> [1,2,3] [1,2,3] -> [2,3,1][2,3,1] -> [3,1,2]count 2번째 였던 3이 출력

내가 원했던 문서가 출력되었으므로 연산을 종료

 

3번째 입력을 보겠습니다

6개의 문서중에서 0번째(인덱스) 문서가 언제 출력되는가를 보겠습니다

우선순위는 [1,1,9,1,1,1] 입니다. 같은 우선순위의 수들이 있어서 설명이 헷갈릴 수 있으므로 0번째 인덱스였던 문서에 대하여 붉은색으로 표시했습니다 

[1,1,9,1,1,1] -> [1,9,1,1,1,1]

 [1,9,1,1,1,1] ->[9,1,1,1,1,1] 

 

처음으로 출력되는 문서는 우선순위가 9였던 문서가 출력  

[9,1,1,1,1,1] -> [1,1,1,1,1]

 

우선순위가 모두 같기 때문에 앞에 있는 수가 2번째로 출력

[1,1,1,1,1] -> [1,1,1,1]

 

우선순위가 모두 같기 때문에 앞에 있는 수가 3번째로 출력

[1,1,1,1] -> [1,1,1]

 

우선순위가 모두 같기 때문에 앞에 있는 수가 4번째로 출력

[1,1,1] -> [1,1]

 

우선순위가 모두 같으면서 내가 원했던 수는 5번째로 출력

[1,1] -> [1] 가 되면서 연산은 종료!

 

이제 생각할 수 있는 것은 내가 지정한 문서의 위치가 맨 앞에 있으면서 가장 높은 우선순위가  내가 지정한 문서의 우선순위과 같을 때 종료가 됩니다.

만약 내 우선순위보다 같거나 높지만 내 문서가 아닌 다른 문서가 앞에 있는 거라면 그것은 pop을 시켜주고 출력된 문서의 수 count를 +1씩 늘려줍니다. 

만약 우선순위가 높지도 않은데 맨 앞에 있는 문서라면 그 문서는 pop 시킨 후에 맨 뒤로 보내버립니다

여기서 주의해야 할 점은!! 만약 내 문서가 맨 앞에 위치해서 출력되려고 하지만 우선순위가 더 높은 것이 큐에 아직 남아있다면 아직 내가 출력될 차례가 아니므로 맨 뒤로 보내야 한다는 것입니다.

이에 유의하여 코드를 작성해봤습니다.

풀이

from collections import deque

iteration = int(input())
priorityQueue = []
problemQueue = 0
nmList = []
for _ in range(iteration):
    N, M = map(int, input().split())
    nmList.append((N,M))
    priorityQueue.append(list(map(int,input().split())))

for i in range(iteration): #문제순회
    problemQueue = deque(priorityQueue[i])
    curPos = nmList[i][1]
    cnt = 1
    while True:
        if curPos == 0 and max(problemQueue) == problemQueue[curPos]:
            print(cnt)
            break

        if problemQueue[0] == max(problemQueue):
            x = problemQueue.popleft()
            cnt += 1
        else:
            tmp = problemQueue.popleft()
            problemQueue.append(tmp)

        curPos -= 1

        if curPos < 0:
            curPos = len(problemQueue) - 1

내 문서의 위치를 curPos로 선언해주어서 계속  내 문서의 위치를 추적합니다. 큐가 pop이 될 때마다 내 위치는 1칸씩 앞으로 당겨집니다. 나보다 더 높은 우선순위의 문서가 있다면 내가 [0]의 위치에 있더라도 맨 뒤로 보내야 합니다. 맨 뒤로 보내면서, 내 위치는 len(큐) -1 마지막 인덱스 위치에 있다고 선언해줘야 합니다!

queue는 FIFO이기때문에 앞에서 빼주는 것이므로 쉽게 해결하고자 popleft()가 구현되어있는 deque를 활용했습니다.