[BOJ] 프린터 큐

TC = int(input())

for tc in range(TC):
    N, M = map(int, input().split())
    arr = list(map(int, input().split()))     # 우선순위 입력받기
    q = [[0]*2 for _ in range(N)]             # 우선순위와 인덱스 값을 새롭게 저장할 이차원 리스트
    cnt = 0                                   # 문서가 몇 번째로 인쇄되는지 체크할 변수

    for i in range(N):
        q[i][0] = arr[i]                      # q에 첫번째 인덱스에는 우선순위를 저장하고,
        q[i][1] = i                           # 두번째 인덱스에는 인덱스 값을 저장함

    while True:           
        x, y = max(q)                         
        if q[0][0] == x:                      # q에 맨 앞에 있는 값이 최댓값이라면
            if q[0][1] == M:                  # 찾아야하는 문서(M)인지 확인하고,
                cnt += 1                      
                print(cnt)                    # 출력
                break
            else:                             # 찾아야하는 문서(M)가 아니라면,
                q.pop(0)                      # q에서 제거만 함
                cnt += 1
        else:                                 # q에 맨 앞에 있는 값이 최댓값이 아니라면
            a, b = q.pop(0)                   # 맨 앞에서 꺼내고, 
            q.append([a, b])                  # 가장 끝으로 옮겨주기

문제 풀이

우선순위가 높은 값부터 순서대로 q에서 제거(문서 출력)하는 방법 사용
q에서 제거하면서 cnt + 1 을 하는데, 이 cnt 값은 몇 번째로 인쇄되는지 체크하는 것.

1) 이차원 리스트 q를 만들고, 첫번째 인덱스에는 우선순위를, 두번째 인덱스에는 인덱스 위치 값을 저장함.
2) 우선순위가 최댓값이면 해당 값이 확인해야 하는 인덱스(M)인지 체크하고,
3) M이 맞다면 cnt + 1 하고, 출력
4) 최댓값은 맞지만 인덱스가 M이 아니라면 찾는 값이 아니므로, q에서 꺼내기만 하고, cnt + 1
5) 우선순위가 최댓값이 아니라면 아직 출력되면 안되므로 q에 맨끝으로 옮겨줌.

 

처음에 최댓값인지 확인할 때, if q[0][0] == max(q):로 작성했는데, 이렇게 하면 우선순위가 같을 때 인덱스 값이 작으면 출력되지 않는 문제가 발생한다. 그러므로 먼저 값을 꺼내고, "x, y = max(q)" 우선순위 값(x)만 비교했다.