백준 1021번 - 회전하는 큐

회전하는 큐 문제 바로 가기

풀이 날짜: 2026-03-17

baekjoon 알고리즘 문제 풀이

풀이 코드


from collections import deque

n,m = map(int, input().split())
num = list(map(int, input().split()))

q = deque(range(1,n+1))
count = 0

for i in num:
    idx = q.index(i)

    if idx <= len(q) // 2:
        q.rotate(-idx)
        count += idx
    else:
        q.rotate(len(q) - idx)
        count += len(q) - idx

    q.popleft()
print(count)

문제 접근

이 문제는 1부터 N까지의 수가 들어있는 큐에서 특정 수들을 순서대로 꺼낼 때, 큐를 왼쪽 또는 오른쪽으로 회전시키는 최소 횟수를 구하는 문제이다. 단순히 값을 제거하는 것이 아니라, 원하는 값을 큐의 맨 앞까지 이동시킨 후 제거해야 한다.

핵심 아이디어

각 단계마다 현재 큐에서 목표 값의 위치를 확인한 뒤, 왼쪽으로 이동할지 오른쪽으로 이동할지를 결정하는 것이 핵심이다. 큐의 앞쪽에 가까운 경우에는 왼쪽 회전이, 뒤쪽에 가까운 경우에는 오른쪽 회전이 더 효율적이다. 즉, 현재 위치(index)를 기준으로 왼쪽 이동 횟수와 오른쪽 이동 횟수를 비교하여 더 작은 값을 선택하는 방식으로 진행한다.

회전 기준 정리

현재 큐에서 타겟의 위치를 idx라고 할 때 다음과 같이 했다.

왼쪽 이동 횟수: idx
오른쪽 이동 횟수: len(queue) - idx

deque와 rotate 활용

이 문제는 양방향에서 원소를 추가/삭제할 수 있는 deque 자료구조를 사용하는 것이 핵심이다. 특히 rotate() 함수를 활용하면 반복문 없이도 큐를 한 번에 회전시킬 수 있어 코드가 간결해진다.

rotate(-k) → 왼쪽으로 k칸 이동
rotate(k) → 오른쪽으로 k칸 이동

내가 헷갈렸던 부분

처음에는 특정 숫자를 꺼내기 위해 “몇 칸 이동해야 하는지”를 직접 이동 거리처럼 생각했지만, 실제로는 큐 자체를 회전시켜서 값을 앞으로 가져오는 개념이었다. 또한 오른쪽 이동 횟수가 단순히 거리로 계산되는 것이 아니라 len - idx로 계산된다는 점이 처음에는 직관적이지 않았지만, 큐가 원형 구조처럼 동작한다고 생각하면 쉽게 이해할 수 있었다.

Vienna sausage