파이썬 Deque와 List의 pop( )

Deque 란?

파이썬의 collections 모듈에는 다양한 자료들이 들어있다. 그 중 하나가 Deque(덱)이다. 

Deque는 A Double-ended Queue 라는 뜻으로, 양 쪽에 원소를 추가하거나 삭제할 수 있어서 

자료구조 중에 queue와 stack을 파이썬에서 쓸 수 있게 해주는 자료이다. 

queue는 선입선출의 자료구조이고, stack은 후입선출의 자료구조인데, Deque에는 이 두개의 자료구조 특징을 만족시키는 메소드들이 있다. (appendleft(), popleft(), append(), pop())

 

나는 프로그래머스의 '두 큐 합 같게 만들기' 문제를 풀면서 deque를 사용했다. 

https://school.programmers.co.kr/learn/courses/30/lessons/118667#

프로그래머스

처음에는 deque를 쓰지 않고 파이썬의 기본 list를 이용해서 답안 코드를 작성했다. 

list의 append 메소드와 pop(0)을 이용하면, 원소 삽입은 가장 꼬리부분에, 원소 추출은 가장 머리부분에서 가능하다고 생각했기 때문이다. 

그런데 답안 제출을 해보니, 시간초과로 실패하는 경우가 너무 많았다. 

list의 pop() 메소드가 인덱스로 원소를 추출하는 것이기 때문에 시간 복잡도가 O(1)일 거라고 생각했는데, 찾아보니 그렇지 않았다. 

 

Deque의 pop VS List의 pop

결론부터 말하자면 deque를 사용하는것이 속도면에서 더 빠르다. 

list에서 가장 마지막 원소를 추출할 때 pop메소드를 쓴다면 시간 복잡도가 O(1)이지만, 그렇지 않은 경우에는 O(n)이다. 

그 이유는 아래 그림과 같다. 

리스트는 pop을 통해 원소를 추출하고 나면, 그 자리를 메꾸기 위해 원소들의 인덱스 이동이 일어나야 한다. 

그렇기 때문에 최악의 경우 O(n) 시간복잡도를 갖게 된다. 

 

반면에 deque에서 popleft를 사용하면 O(1) 시간복잡도로 맨 첫 번째 원소를 추출할 수 있다. 

그 이유는 deque는 double linked list로 구현되어 있기 때문이다. 

그러므로 자료구조 큐로써는 deque를 사용하는것이 list를 사용하는것보다 훨씬 효율적이다.