1. 문제

---

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/1021

2. 아이디어

---

• deque 활용

  1. 오른쪽이든 왼쪽이든 최소 회전 횟수를 구하는 게 목표
  2. 큐의 첫 번째 원소에 목표 숫자가 있는지 확인한 후 있다면 popleft()
  3. 없다면 leftMove에 a가 위치한 que의 인덱스를 넣어주고 rightMove에는 그 나머지를 넣어준다.
  4. 만약 leftMove가 크다면 que를 rightMove만큼 rotate시키고 목표 숫자를 popleft()한 후 회전한 숫자인 rightMove를 더해준다. 반대의 경우라면 반대로!

• example

  rotate(-3) : [4, 5, 6 ,7 ,8 ,9 , 10, 1, 2 ,3]
  rotate(3) : [8, 9, 10, 1 ,2 ,3 ,4 ,5 ,6 ,7]

3. 코드

---

mine

import sys
from collections import deque

input = lambda: sys.stdin.readline()
n, m = map(int, input().split())
arr = list(map(int, input().split()))
que = deque([x for x in range(1, n + 1)])
result = 0

for a in arr:
  if a == que[0]:
      que.popleft()
      continue
  leftMove = que.index(a)
  rightMove = len(que) - leftMove
 
  if leftMove > rightMove:
    que.rotate(rightMove)
    que.popleft() 
    result += rightMove
  else:
    que.rotate(-leftMove)
    que.popleft()
    result += leftMove   
       
print(result)