문제풀이/자료구조
[Python/파이썬] 백준 1021번 회전하는 큐
딜레이레이
2024. 5. 1. 10:48
https://www.acmicpc.net/problem/1021
코드
from collections import deque
n, m = map(int, input().split())
pop_nums = list(map(int, input().split())) # 뽑아내려고 하는 수의 위치
arr = deque([i for i in range(1, n+1)]) # 가장 처음 큐에서의 위치를 표시
ans = 0
for i in range(m):
for j in range(len(arr)): # 뽑으려는 원소의 현재 위치 찾기
if arr[j] == pop_nums[i]:
idx = j
break
if idx < len(arr)-idx: # 2번 연산만 하는게 빠를 때
arr.rotate(-idx)
ans += idx
arr.popleft()
else:
arr.rotate(len(arr)-idx) # 3번 연산만 하는게 빠를 때
ans += len(arr)-idx
arr.popleft()
print(ans)
뽑으려는 수의 위치를 입력으로 주기 때문에 처음에 배열을 [1,2,3,..., N]으로 두고 위치==원소값으로 생각하고 풀면 편하다.
수를 뽑을 때마다 왼쪽으로만 배열을 회전시키거나 오른쪽으로만 배열을 회전시켜야 최소로 연산을 하고 뽑아낼 수 있기 때문에 현재 상태의 배열에서 뽑으려는 수의 위치를 찾아서 거기서 왼쪽 끝과 오른쪽 끝 중 어디가 더 가까운지 구해서 rotate 함수로 회전시켜준다.