백준넷 "회전하는 큐" 문제(1021번) 풀이

알겠습니다. 백준 온라인 저지의 "회전하는 큐" 문제(1021번)를 자세히 살펴보겠습니다. 🙂

문제 개요

• 문제 번호: 1021번
• 문제 제목: 회전하는 큐
• 문제 내용: 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있습니다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 합니다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있습니다:
  1. 첫 번째 원소를 뽑아낸다.
  2. 왼쪽으로 한 칸 이동시킨다.
  3. 오른쪽으로 한 칸 이동시킨다.

입력

• 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ N)
• 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. (1 ≤ 위치 ≤ N)

출력

• 지민이가 M개의 수를 뽑아내는데 드는 최소 이동 횟수를 출력한다.

문제 해결 방법

1. 큐를 구현하기 위해 deque 모듈을 사용합니다.
2. 각 숫자의 위치를 큐에 저장합니다.
3. 뽑아내려는 숫자의 위치와 큐의 첫 번째 원소의 위치를 비교하여 최소 이동 횟수를 계산합니다.
4. 계산된 이동 횟수를 누적하여 최종 결과를 출력합니다.

 

 

 

 

 

 

 

 

 

 

from collections import deque

N, M = map(int, input().split())
target_nums = list(map(int, input().split()))

queue = deque(range(1, N+1))
result = 0

for num in target_nums:
    left_count = queue.index(num)
    right_count = len(queue) - left_count
    
    if left_count < right_count:
        queue.rotate(-left_count)
    else:
        queue.rotate(right_count)
    
    queue.popleft()
    result += left_count

print(result)





#출력
1 2 3 4 5
4 1 2 3 5
14