백준 1021 회전하는 큐 (파이썬 / 자료구조)

1021번: 회전하는 큐 (acmicpc.net)

1021번: 회전하는 큐

from collections import deque
result = 0
N, M = map(int, input().split())
deq = deque(i for i in range(1, N + 1))
lst = list(map(int, input().split()))

for i in range(M):
    if deq.index(lst[i]) < len(deq) / 2:
        while (deq[0] != lst[i]):
            deq.append(deq.popleft())
            result += 1
    elif deq.index(lst[i]) >= len(deq) / 2:
        while (deq[0] != lst[i]):
            deq.appendleft(deq.pop())
            result += 1
    deq.popleft()
print(result)

deque를 이용해서 가장 적은 회전을 통해 구해야 하는 숫자들을 뽑아내야 하는 문제였다..

무엇보다 문제인 것이 인덱스를 참조할때 시간복잡도가 커지지 않을까 해서 고민이었는데

deque의 index함수로 참조를 하면 시간복잡도가 O(1)로 크지 않다고 한다.

이를 잘 알고 있다면 쉬운 문제였다.