[백준/Python] 회전하는 큐

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

1021번: 회전하는 큐

from collections import deque

n, m = map(int, input().split())
value = list(map(int, input().split()))
deque = deque([i+1 for i in range(n)])
count = 0 # 2, 3번 연산의 최소 횟수

for v in value:
	if v == deque[0]: # 찾는 수와 첫번째 값이 같다면 값 뽑기
		deque.popleft()
		continue

	idx = deque.index(v) # 찾는 수의 위치
	if idx > len(deque) // 2: # 뒤에서 앞으로 옮기는 것이 효율적인 경우 -> 오른쪽 이동
		deque.rotate(len(deque) - idx)
		count += (len(deque) - idx)
	else: # 앞에서 뒤로 옮기는 것이 효율적인 경우 -> 왼쪽 이동
		deque.rotate(-idx)
		count += idx
	deque.popleft() # 이동이 끝나면 값 뽑기

print(count)

큐를 사용하는 문제이지만 deque의 rotate 함수를 사용하기 위해 deque을 사용해서 문제를 풀었다.

 

1. n까지의 숫자를 담은 덱을 생성한다.

2. 찾으려는 숫자를 찾고 2, 3번 연산의 최소 횟수를 계산한다.

    2-1. 찾는 수(v) == deque의 첫번째 값(deque[0]) 라면 숫자를 뽑고 다음 찾는 수로 넘어간다.

    2-2. 위의 조건에서 같지 않다면 찾는 수의 위치를 구한다.

    2-3. 찾는 수의 위치가 전체 길이의 절반보다 길다면 뒤에서 앞으로 옮기는 것이 효율적이다. -> 따라서 len(deque) - idx 만큼 오른쪽으로 이동

    2-4. 찾는 수의 위치가 전체 길이의 절반보다 짧다면 앞에서 뒤로 옮기는 것이 효율적이다. -> 따라서 idx만큼 왼쪽으로 이동

    2-5. 이동한 만큼 count에 값을 추가한다. 

    2-6. 이동이 끝나면 값을 뽑는다.

3. 결과를 출력한다.