(큐, 덱) 회전하는 큐

이 문제의 저작권은 BAEKJOON에 있습니다.

 

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

문제는 위 링크에서 확인할 수 있습니다.

from collections import deque

def cheker(j):
    global cnt
    rot = 0
    rot_num = 0

    if len(q) // 2 < q.index(j):
        # rotate(1)방향 회전
        rot = 1
        cnt += len(q) - q.index(j)
        rot_num = len(q) - q.index(j)
    else:
        rot = -1
        cnt += q.index(j)
        rot_num = q.index(j)
    move_Q(rot_num, rot)

def move_Q(rot_num, rot):
    for _ in range(rot_num):
        q.rotate(rot)
    q.popleft()
 
N, M = map(int, input().split())
my_list = list(map(int, input().split()))
q = [i for i in range(1, N+1)]
q = deque(q)
cnt = 0
for j in my_list:
    #j가 현재 없애야 할 수
    cheker(j)

print(cnt)

 

큐가 어느 방향으로 회전하도록 할것인지가 가장 중요했습니다.

큐의 전체 크기를 2로 나누고 pop해주어야 할 요소의 index와 비교했습니다.

비교해서 index값이 더 크면 rotate(1) ←방향으로 회전하도록 했고

index값이 작이면 rotate(-1) → 방향으로 회전하도록 했습니다.