[파이썬/Python] Collections - Deque

들어가며

• 코딩테스트에 응시할 때 빠르게 찾아볼 수 있도록 따로 정리한 내용입니다. 공부하시기에는 빈약한 내용일 수 있음을 미리 알려드립니다.
• 공식 문서를 참고할 때에는 대부분의 기업이 이용하고 있는 프로그래머스 코딩테스트 환경에 적용된 python 3.8 버전의 collections을 참고했습니다.
• 코딩테스트용으로 작성한 글인 만큼 빠르게 훑을 수 있어야 하므로 경어체를 사용하지 않겠습니다.

 

초기화 방법

1. 기존의 iterable 객체 없이 빈 큐를 초기화

from collections import deque

queue = deque()
print(d)
# deque([])

 

2. 기존의 iterable 객체 없이 큐를 구현하되, 구현하면서 임시의 iterable 객체를 이용하여 초기화

from collections import deque

queue = deque([1, 2, 3])
print(queue)
# deque([1, 2, 3])

 

3. 기존의 iterable 객체를 활용하여 큐 초기화

from collections import deque

lst = [i for i in range(5)]
queue = deque(lst)
print(queue)
# deque([0, 1, 2, 3, 4])

 

지원 메서드

• 코딩테스트 문제를 풀면서 한 번도 쓰지 않았거나 개인적으로 코딩테스트 문제 풀이에는 그다지 필요 없다고 생각하는 메서드는 과감히 생략
• 시간복잡도 부분에 파란색은 공식 문서에 적혀 있는 시간복잡도이며, 빨간색은 개인적인 생각에 근거한 시간복잡도.
  즉, 빨간색 글씨는 믿지 않는 것이 좋음
• 시간복잡도 참고 레퍼런스 : python 공식 wiki

 

메서드	설명	시간복잡도	비고
append(x)	큐의 오른쪽에 원소 x 하나를 추가	O(1)
appendleft(x)	큐의 왼쪽에 원소 x 하나를 추가	O(1)
count(x)	큐 내에 x와 일치하는 원소의 개수 return	O(n)	queue 내부의 원소를 전부 순회해야 하므로 O(n)이라고 판단
extend(iterable)	큐의 오른쪽에 iterable 객체를 확장	O(k)	k = iterable 객체의 길이
extendleft(iterable)	큐의 왼쪽에 iterable 객체를 확장	O(k)	k = iterable 객체의 길이
index(x[, start[, stop]])	큐 내에 x가 위치하는 인덱스 return	O(k)	· k = start - stop · start와 stop이 인자로 주어지지 않으면 기본적으로 큐의 모든 원소를 순회 · 탐색 범위 내에 x가 존재하지 않을 경우 ValueError  return
pop()	큐의 오른쪽에서 원소 하나를 제거하며 return	O(1)	원소 없을 경우 IndexError  return
popleft()	큐의 왼쪽에서 원소 하나를 제거하며 return	O(1)	원소 없을 경우 IndexError  return
remove(x)	큐의 왼쪽으로부터 가장 먼저 발견된 x 제거	O(n)	x가 발견되지 않을 경우 valueError  return
rotate(k)	· 큐 내의 원소를 우측으로 k만큼 이동 · n이 음수일 경우 좌측으로 k의 절대값 만큼 이동	O(k)	· k의 기본값은 1 · 내부적으로는 k번 만큼 appendleft(d.pop()) 혹은 append(d.popleft())을 수행

 

추가 팁

• len 메서드 사용 가능
• list나 str, tuple, set과 같은 iterable 객체로 캐스팅 가능
• 단, str으로 캐스팅 할 일이 있다면 약간 손을 봐야 되는데 다음과 같은 형태로 할 수 있음. 예시일 뿐 더욱 효율적인 방법이 존재할 수 있고, 사실 백준이나 프로그래머스 등의 사이트에서 이런 과정을 거칠 일은 단 한 번도 없었음

from collections import deque

d = deque([i for i in range(5)])
print(d) # deque([0, 1, 2, 3, 4])

print(list(d)) # [0, 1, 2, 3, 4]
print(str(d)) # deque([0, 1, 2, 3, 4])

result = str(list(d))[1:-1].replace(', ', '')
print(result) # '01234'