딕셔너리를 이용해 {인덱스: 중요도} 로 풀려고 시도했다. => 중요도가 중복되는 것들이 많아서 key value 로 풀기 어려움.
queue 를 이용하기로 하자
import sys
t = int(sys.stdin.readline().strip()) # 테스트케이스의 수
for i in range(t):
n, m = map(int, sys.stdin.readline().split())
imp = list(map(int,sys.stdin.readline().strip().split())) #queue
cnt = 1
while True:
if m !=0:
if imp[0] == max(imp):
cnt+=1
else :
imp.append(imp[0])
del imp[0]
m-=1
else:
if imp[0] == max(imp):
print(cnt)
break
else:
imp.append(imp[0])
del imp[0]
m = len(imp)-1
큐를 이용해 풀이해봤는데 정답은 맞았지만
뭔가 또 중복 코드가 많고 지저분하다.
타 풀이들 보다 성능도 떨어지는 느낌ㅜ
import sys
from collections import deque
t = int(sys.stdin.readline().strip())
for i in range(t):
n, m = map(int, sys.stdin.readline().split())
imp = deque(map(int,sys.stdin.readline().strip().split()))
cnt = 0
while imp:
if imp[0] == max(imp):
cnt += 1
if m == 0:
print(cnt)
break
else:
imp.popleft()
m -= 1
else:
imp.rotate(-1) # 맨뒤로가
m = (m - 1) % len(imp)
while imp: 로 pop할때 imp가 비어있는지 걱정하지 않아도 된다.
리스트로 만든 큐에서 계속 del[0]을 사용하기보다
deque 을 채택해 popleft()로 앞에서도 pop할 수 있게 만든다.
=> 양끝 엘리먼트(element) 삽입, 제거를 할때
리스트(list)는 O(n)이 소요 but 데크(deque)는 O(1)로 매우 빠름
m= len(imp) - 1 이면 회전 후 m이 len(imp)와 같아 범위를 벗어난다.
그래서 안전하게 (m-1) % len(imp) 을 사용하는것!
이해가 되지 않는다면 예시를 보자
Queue [2, 1, 4, 3]라고 하고
queue[2]에 있는 우선순위 4를 위치를 찾는다고 하자
한 회전 후에 Queue는 [1, 4, 3, 2].
우선 순위가 4인 문서가 이제 queue[1]에 있다.
=> m 값을 하나 당겨야해!
만약 회전 전 m이 len(imp) - 1이면(여기선 3) 회전 후 m은 len(imp)와 같을 것이다.
=> rotate 기 때문에 큐의 len은 달라지지 않거든.
index 초과 에러 발생!
한편 (m - 1) % len(imp) 에서 m-1 < len(imp)이다. 항상!
따라서 모듈러 연산값은 큐를 넘지 않으면서 항상 m-1
deq = deque([1, 2, 3, 4, 5])
deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4]) 양수면 맨앞으로가
deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5]) 음수면 맨뒤로가
# 참고 출처: https://chaewonkong.github.io/posts/python-deque.html