[파이썬, Python] 백준 1021: 회전하는 큐

문제

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
idx = list(map(int, input().split()))
q = deque(i for i in range(1, n+1))
cnt = 0

for i in idx:
    while True:
        if q[0] == i:
            q.popleft()
            break
        else:
            if q.index(i) < len(q)/2:
                while q[0] != i:
                    q.append(q.popleft())
                    cnt += 1
            else:
                while q[0] != i:
                    q.appendleft(q.pop())
                    cnt += 1
print(cnt)

설명

큐를 사용해서 풀이를 해야 하므로 deque을 import 해준다.

입력값을 받아주고 1부터 n+1까지의 큐를 생성해 준다.

입력받은 위치의 값을 기준으로 반복문을 돌려준다.
만약 큐의 제일 첫 번째 수가 목표 숫자라면 큐에서 제거해 주고 반복문을 종료하고 다음 숫자로 넘어간다.

그렇지 않은 경우에는 해당 수의 인덱스를 찾아서 더 적게 돌아가는 방향으로 돌려줘야 한다.
예를 들어 [2,3,4,5]라는 큐가 있다고 가장하자.
3을 뽑아야 한다고 하면 왼쪽으로 돌리는 게 더 최소 횟수일 것이고(2번 연산),
5를 뽑아야 한다고 하면 오른쪽으로 돌리는게 더 최소 횟수일 것이다(3번 연산).

따라서 이를 계산할 방법이 필요한데,
해당 수의 인덱스를 기준으로 현재 큐의 개수를 반으로 나눈 것(중간 지점) 보다 작다면 왼쪽으로,
크다면 오른쪽으로 돌려준다.
큐를 돌리는 과정이 진행되면 cnt를 늘려줘서 연산이 몇 번 수행되었는지 알 수 있게 한다.

최종적으로 카운트된 연산 횟수를 출력하면 된다.