💡문제 분석 요약

중요도가 들어있는 리스트에 특정 인덱스에 있는 값이 몇 번째에 인쇄가 되는지 구해야 한다.

이때 리스트는 큐 방식으로 맨 앞에 있는 것부터 나오게 된다. 맨 앞에 있는 것이 중요도가 가장 높으면 인쇄, 그렇지 않으면 맨 뒤로 재배치한다.

💡알고리즘 설계

반복문에 들어가기 앞서, 인덱스 번호와, 중요도 정보를 tuple로 만들어 담은 pList(deque 형태)를 만든다.

1. 중요도 값 중 가장 큰 값을 max_num 변수에 초기화한다.
2. 현재 pList에서 맨 앞에 있는 tuple의 중요도를 max_num과 비교한다.
3. max_num과 같다면(가장 큰 값이라면), find(알고자 하는 idx)와 맨 앞에 있는 tuple의 idx와 비교한다.

3-1) 같다면(알고자 하는 idx이고 현재 인쇄해야 한다.), ans를 출력하고 반복문을 빠져나간다.

3-2) 같지 않다면(가장 큰 값이라 인쇄해야 하지만 찾고자 하는 idx가 아니다.), pList 큐 리스트에서 pop시킨다.

1. 맨 앞에 있는 tuple의 중요도가 max_num이 아니라면, pop을 하고, 그 값을 다시 맨 뒤에 append한다.

💡코드

import sys
from collections import deque

T = int(sys.stdin.readline())

for _ in range(T):
    n, find = map(int, sys.stdin.readline().split())
    num = list(map(int, sys.stdin.readline().split()))
    idx = 0
    ans = 1
    pList = []
    for i in range(n):
        pList.append((i, num[i]))
    pList = deque(pList)

    while True:
        max_num = max([item[1] for item in pList])
        if pList[0][1] == max_num:
            if pList[0][0] == find:
                print(ans)
                break
            pList.popleft()
            ans += 1
        else:
            pList.append(pList.popleft())

💡시간복잡도

테스트 케이스 수를 T로 치면,

시간 복잡도는 O(T * n^2)이다.

가장 바깥 for문의 시간 복잡도가 T이고 그 안에는

1. n만큼에 시간이 걸리는 pList 초기화 시키기
2. 최대 n만큼 걸리는 while문 + while문 안에 최대 값을 찾는 데 최대 n ⇒ O(n*n)