[백준-실버4] 1021번 회전하는 큐(큐, deque, 파이썬)

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

1021번: 회전하는 큐

 

<내 코드>

- idx_list에 뽑아야할 수의 인덱스를 저장했다.(이 때 문제 인덱스는 1부터 n 임을 주의)

- queue는 인덱스를 나타낸다. 따라서 1-n까지의 값을 넣어주었다.

- idx_list를 순회하면서 어느 방향으로 회전하는게 최소인지 파악한다.

- left는 큐에서 뽑아야하는 idx의 인덱스를 나타낸다. 

- right는 left(현재 위치)를 제외하고 오른쪽으로 어느 정도 길이인지 확인한다.

- 이 때, left가 0인 경우 회전 없이 바로 출력가능하기때문에 pop한다.

- 만약 왼쪽이 더 짧거나 같다면 큐를 왼쪽으로 회전시킨다. queue.rotate(-num) -> 왼쪽 회전 의미

  그리고 left값 만큼 cnt에 더해준다.

- 오른쪽이 더 짧은 경우 오른쪽으로 회전시키는데 이 때 값이 맨 앞으로 오려면 right +1만큼 회전해야하고

  cnt에도 right+1값을 더해준다.

 

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

n, m = map(int, input().split())
idx_list = list(map(int, input().split()))
queue = deque(list(i for i in range(1,n+1)))
cnt = 0
for idx in idx_list:
    # 현재 원소 기준으로 왼쪽 오른쪽 길이 파악
    left = queue.index(idx)
    right = len(queue) - (left+1)
    
    if left ==0:
        queue.popleft()
        
    elif left <=right: # 왼쪽으로 이동하는게 유리할때
        queue.rotate(-left)
        queue.popleft()
        cnt+=left
    else:
        queue.rotate(right+1)
        queue.popleft()
        cnt+=right+1
        
print(cnt)