백준 알고리즘 1966: 프린터 큐(Python)

www.acmicpc.net/problem/1966

1966번: 프린터 큐

---

문제 해결을 위한 과정

이 문제의 경우 큐를 이용하여 문제의 조건을 잘 작성해주면 정답을 받을 수 있는 문제였습니다.

파이썬에서 큐를 이용하기 위해서는 from collections import deque 코드의 윗부분에 첨가합니다.

먼저 입력받은 n개의 숫자들을 중요도와 묶어서 큐에 append 해줍니다. 그 후 큐를 조회하면서 뒤쪽에 더 높은 우선순위를 가진 작업이 존재할 경우 큐에서 popleft()를 해준 후 뒤쪽에 append 해줍니다. 반면 뒤쪽에 더 높은 우선순위를 가진 작업이 존재하지 않다면 바로 출력을 해줍니다. 이때 출력을 하기 전 popleft를 해준 후 popleft 된 작업의 번호와 입력받은 원래의 작업들 중에서 m번째 존재하는 값이 값다면 count를 출력해주고 값이 같지 않다면 count를 하나 증가시키는 것으로 해결합니다. 

---

소스코드

 

from collections import deque
 
tc = int(input())
for i in range(tc):
    q = deque()
    n, m = map(int, input().split())
    priority = list(map(int, input().split())) 
    a = 1
    for p in priority:
        q.append((a, p)) # 우선순위와 쌍으로 결합하여 큐에 append한다.
        a += 1
    i = 0
    count = 1
    while i < len(q):
        check = True
        for j in range(i, len(q)): # 뒤쪽에 더 높은 우선순위를 가진 작업을 찾는다 
            if q[i][1] < q[j][1]:
                a, p = q.popleft()
                q.append((a, p))
                check = False
                break
        if not check: # 더 높은 우선순위를 가진 작업이 없는 경우
            i = 0
        else: # 더 높은 우선순위를 가진 직업이 존재하는 경우
            a, p = q.popleft()
            if a == 1 + m: # m번째 작업이 popleft한 작업과 같은 경우 count를 출력
                print(count)
                break
            else: # m번째 작업이 popleft한 작업과 다른 경우 count를 하나 증가시켜줌
                count += 1
            i = 0