📘 백준 1021번: 회전하는 큐

문제 링크 🔗

📌 문제 설명

양방향으로 회전이 가능한 큐가 주어진다.
처음에는 1부터 N까지의 숫자가 순서대로 들어 있으며, 우리가 꺼내야 할 숫자들이 M개 주어진다.

큐에서 원하는 숫자를 꺼내는 방법은 세 가지:

1. 첫 번째 원소를 바로 뽑는다 (이 연산은 비용이 없음)
2. 왼쪽으로 한 칸 이동시킨다 (2번 연산)
3. 오른쪽으로 한 칸 이동시킨다 (3번 연산)

목표는 숫자들을 뽑는 순서를 지키면서 최소한의 연산으로 꺼내는 것이다.

---

🔍 예시 입력

10 3
2 9 5

→ 큐는 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 뽑아야 할 숫자는 2, 9, 5

---

🧠 문제 접근 방법

이 문제의 핵심은 회전 방향을 효율적으로 결정하는 것이다.

• deque 자료구조를 사용하면 양방향으로 회전이 가능하므로 적합하다.

• 뽑아야 할 숫자가 큐의 어느 위치(index)에 있는지를 확인하고,

  • 앞쪽에 가까우면 → 왼쪽으로 회전
  • 뒤쪽에 가까우면 → 오른쪽으로 회전

  # 왼쪽으로 회전
  q.append(q.popleft())
  
  # 오른쪽으로 회전
  q.appendleft(q.pop()) 

• 원하는 숫자가 맨 앞에 오면 popleft()로 뽑고 종료한다.

---

✅ 코드

from collections import deque

n, m = map(int, input().split())
q = deque([i for i in range(1, n+1)])
targets = map(int, input().split())

count = 0

for target in targets:
    while True:
        if q[0] == target:
            q.popleft()
            break

        index = q.index(target)

        if index <= len(q)//2:
            q.append(q.popleft())
        else:
            q.appendleft(q.pop())

        count += 1

print(count)

---

⚠️ 디버깅 과정

len(q) / 2는 부동소수점 결과를 반환하므로, // 연산자 사용이 더 안전하다.

n/2 사용 → 고정된 기준 사용

# 수정 전 
if index <= n/2:

• 이 조건은 큐 길이가 변해도 n은 그대로이므로, 회전 방향이 틀릴 수 있음.
• 큐 길이가 줄어들수록 회전 판단 기준도 줄어들어야 함.

if index <= len(q) // 2:

---

✨ 배운 점

• deque를 활용하면 양방향 회전 문제를 쉽게 처리할 수 있다.
• 큐의 길이는 계속 줄어드므로, 현재 길이에 따라 회전 방향을 매번 재계산해야 한다.

---