[백준/Python] 1021 회전하는 큐

문제 링크

1021번: 회전하는 큐

 

문제 풀이

• 큐의 맨 앞의 숫자가 현재 뽑고자 하는 숫자가 일치할 때까지 큐를 왼쪽, 오른쪽으로 돌려야(rotate) 한다.
• 만약 큐의 맨 앞의 숫자가 일치한다면 큐를 제거하고(popleft), 그렇지 않다면 어느 방향으로 돌릴 것인지를 정해야 한다.
• 이때, 뽑고자 하는 숫자의 위치가 중간 위치랑 같거나 작다면 왼쪽으로 로테이션하고, 그보다 크다면 오른쪽으로 로테이션을 해야 값이 최소가 된다.

 

전체 코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
queue = deque([x for x in range(1, n+1)])

count = 0
for i in arr:
    k = queue.index(i)
    mid = len(queue) // 2
    while True:
        if queue[0] == i:
            queue.popleft()
            break
        else:
            if k <= mid:
                while queue[0] != i:
                    queue.rotate(-1)
                    count += 1
            else:
                while queue[0] != i:
                    queue.rotate(1)
                    count += 1

print(count)