백준 1021번 "회전하는 큐"

문제

백준 1021번 회전하는 큐

풀이

덱을 이용해 푼 문제.

원하는 원소를 덱에서 뽑아내려면 해당 원소를 덱의 첫번째로 위치시켜야 한다.
이를 위해 덱을 왼쪽에서 오른쪽 혹은 그 반대로 회전시켜야 하는데,
덱을 회전시키는 수를 최소로 줄이기 위해서 해당 원소의 현재 위치가 덱의 가운데에서 왼쪽에 있는지, 오른쪽에 있는지 알아내어
해당 방향으로 회전 시켜주어야 한다.

Python 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))
que = deque([i+1 for i in range(n)])
count = 0

for i in range(m):
  if len(que)/2 > que.index(arr[i]):
    while que[0] != arr[i]:
      que.append(que.popleft())
      count += 1
    que.popleft()
  else:
    while que[0] != arr[i]:
      que.appendleft(que.pop())
      count += 1
    que.popleft()
    
print(count)