[python/파이썬] 백준 1021 회전하는 큐

[문제 출처]

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

1021번: 회전하는 큐

 

[문제 풀이]

deque의 rotate()를 사용하여 회전하는 큐의 연산을 하였다.

rotate의 경우 a.rotate(k)를 하면 오른쪽으로 k만큼 원소들을 이동시킨다. 

즉 문제에서 말하는 3번 연산을 k번 진행하는 것과 동일하다.

k가 음수가 되면 2번 연산과 같은 기능을 하게 된다.

 

n이 주어졌을 때, 1부터 n까지의 수가 저장된 큐를 선언하여 뽑아내고자 하는 숫자의 위치를 파악하도록 하였다.

각 숫자가 큐에서 위치한 인덱스가 어디냐에 따라서 2번과 3번 연산 중에 어느 것이 더 적은 연산을 필요로 하는지가 달라지기에

큐의 가운데를 중심으로 왼쪽에 위치하는지 오른쪽에 위치하는지 확인한 후에 rotate 해주고 popleft 해주었다.  

#1021
from collections import deque
n,m = map(int, input().split())
el = list(map(int, input().split()))

lst = [i for i in range(1,n+1)]
queue = deque(lst)

cnt = 0
for e in el:
  if queue.index(e) >= (len(queue)/2):
    k = len(queue) - queue.index(e)
    cnt += k
    queue.rotate(k)
  else:
    k = queue.index(e)
    cnt += k
    queue.rotate(-k)
  queue.popleft()

print(cnt)