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

문제 링크

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

---

문제

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

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

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

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

---

풀이

원형큐 문제로 deque를 활용한다.

3가지 연산의 의미는 다음과 같다.

1. 첫 번째 원소를 뽑아낸다.

dq.popleft()

2. 왼쪽으로 한 칸 이동시킨다.

dq.rotate(-1)

3. 오른쪽으로 한 칸 이동시킨다.

dq.rotate(1)

뽑아내려고 하는 원소의 위치가 덱의 중간보다 앞이면 2번 연산을, 뒤면 3번 연산을 실행한다.

---

정답 코드

from collections import deque

n, m = map(int, input().split())
idx = list(map(int, input().split()))
dq = deque(range(1, n + 1))
cnt = 0

for i in idx:
    while True:
        if i == dq[0]:
            dq.popleft()
            break
        
        else:
            if dq.index(i) <= len(dq)//2:
                dq.rotate(-1)
                cnt += 1
        
            else:
                dq.rotate(1)
                cnt += 1

print(cnt)

---

알게된 점

왼쪽으로 한 칸 이동을 dq.append(dq.popleft())로 생각했으나 rotate(-1)이 있었다.

마찬가지로 오른쪽으로 한 칸 이동을 dq.appendleft(dq.pop())로 생각했으나 rotate(1)로 나타낼 수 있었다.

rotate()는 덱을 이동시키는 함수이다. 매개변수가 음수이면 왼쪽으로, 양수이면 오른쪽으로 이동한다.

이 문제에서는 한 칸 이동이라 매개변수에 1, -1을 넣었지만 n을 넣으면 n번 이동한다.