처음에 든 생각은 priority queue를 구현해서 그대로 하면 되지 않나? 했는데 test case를 한 번 생각해 보니까 아니었다. 그래서 바로 접었고, 그냥 문제에서 하라는 대로 정확히 일치하는 로직으로 구현하였다.
메인 아이디어는 맨 앞이 배열 안에서 max값인지 아닌지를 체크하는 것이다. max라면 pop(0)
, 아니라면 배열의 맨 뒤로 보낸다.
그리고 매 수행마다 target
의 index
를 추적해야 한다.
최종적으로 출력해야 하는 것은 pop(0)
을 하였을 때 target이 몇 번째로 나오는가 이다.
파이썬에 대해 아직 익숙하지 않아서 입출력을 어떻게 하는지 찾아보았다.
python stdin readline
import sys
test_cases = int(input())
for a in range(test_cases):
# input
n,target = list(map(int,sys.stdin.readline().split( )))
important = list(map(int,sys.stdin.readline().split( )))
count = 0
while True:
if important[0] == max(important):
# 출력
important.pop(0)
count+=1
if target == 0:
break
else:
target -= 1
else:
# 맨 뒤로 넘김
important.append(important.pop(0))
if target == 0:
target = len(important)
target -= 1
print(count)
어려웠던 점은 맨 뒤로 target이 넘어갈 경우 예외처리를 하지 않았었는데, 이를 감지하여 index를 update해 주니 결과가 잘 나왔다.