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

🔒 문제 설명

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

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

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

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

1021번: 회전하는 큐

---

🔓 소스 코드

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
deque = deque([i for i in range(1, N+1)])
arr = list(map(int, input().split()))
count = 0 #정답

for i in arr:
    while True: # 배열의 첫번째 값이 i(뽑아내려고 하는 수)와 같을 때까지 반복
        if deque[0] == i:
            deque.popleft()
            break
        else:
            if deque.index(i) <= len(deque)/2: # 뽑아내려는 값의 위치가 어느 방향으로 회전하는 것이 작은지 비교
                deque.rotate(-1)
                count += 1
            else:
                deque.rotate(1)
                count += 1

print(count)

 

---

🔑 해결 방법

이 문제는 간단하게 생각하면 deque의 rotate를 사용하면 됐다!

rotate는 deque를 회전시켜주는 명령어로 

rotate(1)을 하게 되면 ([1,2,3,4]) 를 ([4, 1, 2, 3]) 으로 변경해주고 rotate(-1)을 하게 되면 ([1,2,3,4])를 ([2, 3, 4, 1])으로 만들어준다. rotate(1)이 아닌 1자리에 다른 정수가 들어가면 그 정수만큼 회전을 해준다.