#1021 회전하는 큐 [백준](H99.30)

📄문제

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

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

첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.

왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.

오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

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

예제 입력1

10 3
1 2 3

예제 출력1

0

🖋️코드

from collections import deque

n, m = map(int, input().split())
que = deque([])
for i in range(1,n + 1):
    que.append(i)
needs = list(map(int, input().split()))
count = 0

for j in range(m):
    while True:
        if que[0] == needs[j]:
            que.popleft()
            break
        loc = que.index(needs[j])	#찾는 숫자

        if loc <= len(que) // 2:	#찾는 숫자 위치가 중간보다 낮으면
                que.rotate(-1)		#앞으로 땡겨라
                count += 1
        else:					
            que.rotate(1)		#아니면 뒤로 땡겨라
            count += 1

print(count)

🧷(나만 알아듣는) 추가설명

파이썬에서 큐 자료구조의 데이터를 list로 사용할때 연산이 느려지므로
deque를 쓰는게 낫다.
deque를 안쓰면 insert , del 로 앞에서 넣고 뒤에서 빼는건 가능하다.
deque를 쓸때는 append , popleft 로 넣고 뺀다.
list.rotate()는 안에 들어간 숫자만큼 앞으로(+)나 뒤로(-) 이동시키는 함수이다.