S3 1021. 회전하는 큐

문제 보기 :  1021번: 회전하는 큐

---

문제

• 정답률 : 61%

 

---

작성 코드

from collections import deque

# 입력 받기
n, m = map(int, input().split())  # 큐 크기 n, 뽑아낼 원소의 개수 m
targets = list(map(int, input().split()))  # 뽑아낼 원소의 위치

# 큐 초기화
que = deque(range(1, n + 1))  # 1부터 n까지의 숫자 포함

answer = 0 # 총 연산 횟수

# 뽑아내기
for target in targets:
    while True:
        if que[0] == target:
            que.popleft()
            break
        else:
            targetidx = que.index(target)
            if targetidx <= len(que)//2:
                que.rotate(-1) # 왼쪽으로 한 칸 이동
                answer += 1
            else:
                que.rotate(1) # 오른쪽으로 한 칸 이동
                answer += 1

print(answer)

---

풀이

1. queue는 deque 자료구조로 초기화하며, 효율적인 삽입 및 삭제를 지원한다.

2. 뽑아낼 대상이 첫 번째 원소가 될 때까지 rotate 연산을 통해 큐를 왼쪽 또는 오른쪽으로 이동한다.

3. 이동 방향은 대상의 현재 위치를 기준으로, 앞쪽과 뒤쪽의 거리 중 짧은 쪽을 선택한다.

4. 총 연산 횟수를 누적하여 출력한다.