[Python] 백준1021번 : 회전하는 큐

💡문제

백준 1021번 문제 링크

🍀풀이

문제를 보고 진짜 딱 덱 문제라는 것을 알 수 있었다.
풀면서도 덱 연습 문제로 너무 좋다고 생각이 들었다.

문제에 나와 있는대로 3가지의 연산을 해야한다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
   -> popleft()
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
   -> append(popleft())
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
   -> appendleft(pop())

이렇게 하면 될거 같다고 생각을 했다. 그리고 2번, 3번 연산의 최솟값을 구해야하는데
뽑아내려고 하는 위치의 인덱스가 큐의 중간을 기준으로 왼쪽에 있는지, 오른쪽에 있는지 확인을 하면 최솟값을 찾을 수 있다.

코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
pos = list(map(int, input().split()))
q = deque([i for i in range(1, n+1)])	# 1부터 n
cnt = 0

for i in pos:
    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)

💡 생각을 더 하자!!!