[백준/1021/파이썬] 회전하는 큐

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

1021번: 회전하는 큐

조건

• 1번: 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. =⇒ a1에서 Pop이 일어남.
• 2번 : 왼쪽으로 한 칸 이동 시킨다. ⇒ 왼쪽으로 rotate, 맨 앞 element는 맨 뒤로 간다.
• 3번 : 오른쪽으로 한 칸 이동 시킨다 ⇒ 오른쪽으로 rotate, 맨 뒤 element는 맨 앞으로 간다.
• 큐의 크기 N, 뽑아 내려고 하는 수의 개수 M,뽑아 내려고 하는 수의 위치가 순서대로 주어짐.

SOL

우선, 해당 조건들을 도식화하면 아래와 같이 됨.

1. 자료들이 배열 형태를 이룬다
2. 자료들이 이동도 하고, 맨 왼쪽에서 PoP이 일어남. (이건 deque 못참지)
3. 최댓값,최솟값 관련 x 해당값이 어디에 있는지 아는게 중요!

파이썬에는 dequeue(double ended queue)가 있기 때문에, 큐의 처음과 끝에서 삽입/삭제가 일어날 수 있으니, dequeue 쓰자.

 

• 첫 번째 index에서 pop이 일어나기 때문에, 첫 번째 인덱스에서, 해당 값을 가지는 인덱스 까지 거리를 생각 해줘야함.
• D(거리) =해당 값을 가지는 인덱스 or D = 배열의 크기 - 해당 값을 가지는 인덱스

from collections import deque

n,m= map(int,input().split())
value = list(map(int,input().split()))
cnt=0 
arr = [x for x in range(1,n+1)]
dq = deque(arr)

for idx in range(len(value)):
	if dq[0]==value[idx]: # 입력된 값의 인덱스가 0에 위치하다면, 바로 뺌.(카운트 x)
		dq.popleft()
		continue
	dq_idx=dq.index(value[idx])
	if dq_idx > len(dq)/2:
		dq.rotate(len(dq)-dq_idx)
		cnt+=(len(dq)-dq_idx)
	elif dq_idx<=len(dq):
		dq.rotate(-dq_idx)
		cnt+=dq_idx
	dq.popleft()
 
 
print(cnt)