[백준] 1021 회전하는 큐

문제

• N개의 원소를 포함한 양방향 큐에서 M개의 수를 순서대로 뽑아내려고 할 때, 움직임의 최솟값은?
  • 1 <= M <= N <= 50
• 연산은 다음과 같다.
  • 1. 첫 번째 원소 뽑아내기
  • 2. 왼쪽으로 한 칸 이동하기
  • 3. 오른쪽으로 한 칸 이동하기

 

풀이

• 1 ~ N 리스트를 생성하고, 해당 위치가 왼쪽/오른쪽 회전 중 가까운 쪽의 개수를 센다.

 

N, M = map(int, input().split())
q = [i for i in range(1, N+1)]          # 큐
answer = 0                              # 정답 변수
# 뽑아낼 숫자 위치 별로
for x in list(map(int, input().split())) :
    now = q.index(x)    # 뽑아낼 숫자의 인덱스
    if now == 0:        # 첫번째면 바로 뽑아내기
        q = q[1:]
        N -= 1  
    else: 
        # 왼쪽 회전과 오른쪽 회전 중 더 작은 값 더하기
        answer += min(now, N-now)
        q = q[now+1:] +  q[:now]
        N -= 1

print(answer)

 

References

• 백준 1021
• 2023.04.28 오늘의 문제