[Python] 백준 2164번으로 알아보는 list 와 deque의 시간 복잡도 차이

백준 2164번 문제(https://www.acmicpc.net/problem/2164)

처음의 이 문제를 보고 list를 이용하여 풀면 되겠구나 하고 다음과 같은 코드로 문제를 풀었다.

n = list(range(1, int(input())+1))
while len(n) != 1:
    del n[0]
    a = n.pop(0)
    n.append(a)
    print(n)
print(n[0])

해당 코드의 결과는 시간 초과였다.

List 와 deque의 시간 복잡도

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.

즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.

컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

deque를 이용한 문제 풀이

n = deque(range(1, int(input())+1,))
while len(n) != 1:
    n.popleft()
    n.rotate(-1)
print(n[0])

첫번째 원소를 popleft()를 이용해 제거를 하고 두번쨰 원소를 저장하고 다시 append할 필요 없이 rotate함수를 이용해 맨 뒷자리로 위치시키면 된다.

deque는 언제 쓰먄 좋을까?

deque는 시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다.

따라서, 대부분의 경우의 deque는 list보다 좋은 옵션이며 특히 push/pop연산이 많을 경우 list보다 좋은 속도를 가진다.