[백준]1021번 회전하는 큐 - 덱

 

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())
deque = deque([])
for i in range(1, n + 1):
    deque.append(i)

a = list(map(int, sys.stdin.readline().split()))
cnt = 0
for i in range(m):
	# 2번 연산이 유리한 경우, 뽑으려는 값이 덱에서의 인덱스가 더 작을 경우
    if deque.index(a[i]) < len(deque) - deque.index(a[i]):  
        while True:
            if deque[0] == a[i]:
                deque.popleft()
                break
            else:
                deque.append(deque.popleft())
                cnt = cnt + 1

    else:  # 3번 연산이 유리한 경우
        while True:
            if deque[0] == a[i]:
                deque.popleft()
                break
            else:
                deque.appendleft(deque.pop())
                cnt = cnt + 1
print(cnt)

 

코드 설명

큐(덱)에는 1~n 의 수가 순서대로 저장 되어있다. 이를 초기화 하기 위해 반복문을 수행하여 준다. 뽑으려는 원소들은 a 라는 리스트에 순서대로 저장하여 준다. 뽑으려는 갯수 만큼 반복문을 수행한다. 2가지의 경우가 있을 수 있다.

1. 왼쪽으로 한 칸 이동시키는 연산이 유리한 경우

2. 오른쪽으로 한 칸 이동시키는 연산이 유리한 경우

어느 것이 유리한지는 인덱스를 통해 판별할 수 있다. 만약 a[i]의 값이 덱에서의 인덱스를 B라고 한다면, B vs (덱의 길이 - B) 를 서로 비교하여 오른쪽이 크다면 왼쪽에 더 가깝다는 뜻이고, 그 반대라면 오른쪽에 더 가까이 위치한다는 뜻이다.

그 후 원소가 같다면 빼내면 될 것이고, 같지 않다면 반복해서 연산을 수행하며 카운트를 해준다.

 

Point : 인덱스를 활용하여 뽑고 싶은 숫자가 왼쪽에 가까운지, 오른쪽에 가까운지 판별하는 기준이 중요하다. 판별을 했다면 반복되는 연산과 카운트를 통해 문제를 쉽게 풀이할 수 있다.