백준 풀이

파이썬 공부

list.pop(0) vs deque.popleft()

list로 queue를 구현하게 되면 가장 왼쪽의 원소를 빼주어야 하기 때문에 pop(0)를 사용하게 된다.

하지만 deque로 queue를 구현하게 되면 popleft()를 사용할 수 있게 되는데 deque.popleft()의 속도가 훨씬 빠릅니다.

이유는 list.pop(0)의 경우 시간복잡도는 O(n) 이지만 deque.popleft()는 O(1)에 매우 가깝기 때문입니다.

list는 내부적으로 C 배열로 구현되어 있으며 특정 요소를 삭제한 뒤에는 나머지 요소들을 정리(reposition)해주어야 합니다. -> O(n)

deque는 내부적으로 이중 연결 리스트(doubly-linked list)로 구현되어 있어서 가장 앞, 가장 뒤의 요소를 추가하고 빼는 것에 특화되어 있습니다. -> 사실상 O(1)