백준 1021 - deque를 이용해서 풀어보았습니다

 

 

 

 

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

 

파이썬 코드

from collections import deque

n, m = map(int, input().split())

deq = deque(i+1 for i in range(n))
li = list(map(int, input().split()))

sum = 0
for i in range(m):
    diff = deq.index(li[0])
    diff_rev = len(deq) - diff

    if diff == 0:
        li.pop(0)
        deq.popleft()
    elif diff < diff_rev:
        deq.rotate(-diff)
        sum += diff
        li.pop(0)
        deq.popleft()
    else:
        deq.rotate(diff_rev)
        sum += diff_rev
        li.pop(0)
        deq.popleft()

print(sum)

 

 

뽑아야 하는 값의 인덱스를 diff로, 전체 deque의 길이에서 diff를 뺀 값을 diff_rev로 놓았습니다.

diff가 0이면 뽑아야 하는 수가 가장 앞에 있다는 의미이므로 리스트와 deque에서 각각 값을 꺼냅니다.

diff 보다 diff_rev가 더 크면 deque를 오른쪽 방향으로 diff_rev 만큼 rotate 시킨 후 값을 꺼냅니다.

반대는 반대로 합니다.