1966 프린터 큐

문제

우선순위가 있는 q에서 index에 해당하는 값이 몇번째로 나오는지 구하는 문제이다.

Link: 프린터 큐

코드

import sys
import _collections

#sys.stdin = open("../input/1966.txt", "r")

n = int(input())
for i in range(n):
    number_of_document, target = map(int, input().split())

    arr = _collections.deque(map(int, input().split()))
    result = False
    count = 0
    while(not result):
        x = False
        #자신보다 중요한게 있는지 검사
        for i in arr:
            if(i > arr[0]):
                x = True
                break

        tmp = arr.popleft()

        if (x): #중요한게 있으므로 빼서 옆에 넣는다.
            arr.append(tmp)
            if (target == 0):
                target = len(arr)-1
            else:
                target -= 1
        else: # 중요한게 없으므로 빼기만 한다.
            count += 1
            if (target == 0):
                result = True
            else:
                target -= 1
    print(count)

풀이

Queue를 활용하여 문제를 풀었고,

맨 왼쪽에 있는 원소보다 높은 우선순위가 존재하면, 다시 오른쪽에 넣는다. 아닐경우에는 넣지 않는다.

이후, 원하는 원소의 위치를 계산한다.

123456789 와 같은 배열이 올 경우 전부 돌아야하므로, 시간 복잡도는 O(n^2)이 될 것이다.