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

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

 

코드

from collections import deque

n, m = map(int, input().split())
pop_nums = list(map(int, input().split()))  # 뽑아내려고 하는 수의 위치
arr = deque([i for i in range(1, n+1)])  # 가장 처음 큐에서의 위치를 표시
ans = 0

for i in range(m):
    for j in range(len(arr)):   # 뽑으려는 원소의 현재 위치 찾기
        if arr[j] == pop_nums[i]:
            idx = j
            break
    if idx < len(arr)-idx:  # 2번 연산만 하는게 빠를 때
        arr.rotate(-idx)
        ans += idx
        arr.popleft()
    else:
        arr.rotate(len(arr)-idx)    # 3번 연산만 하는게 빠를 때
        ans += len(arr)-idx
        arr.popleft()
print(ans)

 

뽑으려는 수의 위치를 입력으로 주기 때문에 처음에 배열을 [1,2,3,..., N]으로 두고 위치==원소값으로 생각하고 풀면 편하다. 

 

수를 뽑을 때마다 왼쪽으로만 배열을 회전시키거나 오른쪽으로만 배열을 회전시켜야 최소로 연산을 하고 뽑아낼 수 있기 때문에 현재 상태의 배열에서 뽑으려는 수의 위치를 찾아서 거기서 왼쪽 끝과 오른쪽 끝 중 어디가 더 가까운지 구해서 rotate 함수로 회전시켜준다.