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

👀 문제

1021번: 회전하는 큐 ✨ 실버 3

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.)

이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

🔑 키포인트

자료 구조 덱

✍️ 코드

# BOJ 1021
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
locations = list(map(int, sys.stdin.readline().split()))

# 양방향 큐
queue = deque([i for i in range(1, n+1)])
count = 0
i = 0

while i < m:
    if queue[0] == locations[i]:
        queue.popleft()
        i += 1
        continue
    else:
        # 현재 위치가 큐의 길이//2보다 작거나 같으면 앞으로 옮겨주는 게 빠르다
        if queue.index(locations[i]) <= len(queue)//2:
            # 왼쪽으로 한 칸 이동 (2번)
            queue.append(queue.popleft())
            count += 1           
        else:
            # 오른쪽으로 한 칸 이동 (3번)
            queue.appendleft(queue.pop())
            count += 1
print(count)