[알고리즘] 큐, 덱 - 백준 1021번 회전하는 큐

정답 코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
loc = list(map(int, input().split()))

arr = deque([i for i in range(1, N+1)])
n, m = 0, 0

for l in loc:
  index = arr.index(l)
  left = index
  right = len(arr) - index - 1

  if left <= right:
    for j in range(left):
      arr.append(arr.popleft())
      n += 1
  else:
    for j in range(right+1):
      arr.appendleft(arr.pop())
      m += 1
  arr.popleft()

print(n+m)

풀이 과정

주어진 설명을 해석하는 것이 가장 어려운 문제였다...!

N = 10, M = 3
loc = [ 2, 9, 5 ]
arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

우리가 arr 배열에서 찾아야 할 숫자는 2, 9, 5 이다.
n은 2번 연산, m은 3번 연산의 개수이다.

먼저 arr에서 2를 찾는다.
2를 기준으로 왼쪽에는 1개, 오른쪽에는 8개의 숫자가 있다.
오른쪽이 더 크기 때문에 2번 연산을 수행한 후, 가장 앞에 있는 원소를 제거한다.

이런식으로 찾아야 할 값의 왼쪽과 오른쪽 원소의 개수를 비교하여 문제를 푼다.