[Python] 회전하는 큐 - 백준

해당 글은 백준 1021번 문제 '회전하는 큐'를 다룬다.

문제

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

1021번: 회전하는 큐

 

설명

해당 문제는 deque로 큐를 생성하고, rotate 함수를 통해 왼쪽 혹은 오른쪽으로 이동해가며 연산의 최솟값을 구하는 문제이다.

queue의 첫번째 원소값이 뽑아내려고 하는 수와 같다면 뽑아내고

아니라면 뽑아내려고 하는 수를 첫번째 원소값으로 이동시키기 위한 왼쪽, 오른쪽 값을 구한다.

연산이 최소가 되어야하므로 l과 r 중 작은 값을 선택하여 rotate를 진행한다.

 

코드

from collections import deque

n, m = map(int, input().split())
num = list(map(int, input().split()))
queue = deque([i for i in range(1, n+1)])

result = 0
while num:
    if num[0] == queue[0]:
        num.pop(0)
        queue.popleft()
    else:
        l = queue.index(num[0])
        r = len(queue)-l
        if l < r:
            queue.rotate(-l)
            result += l
        else:
            queue.rotate(r)
            result += r
print(result)