리스트 회전에 용이한 자료구조 - deque(데크)
데크(deque)의 개념
⇒ 양방향의 Queue로 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다. 데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
시간복잡도 : O(1) time
이는 리스트로 접근할때 (O(n) time) 보다 훨씬 빠른 속도로 접근한다.
데크 언제 쓰는가?
컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우
데크 사용법
from collections import deque
deq = deque(array)
데크(deque)에 존재하는 메서드(method)는 대략 다음과 같다.
deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.deque.remove(item): item을 데크에서 찾아 삭제한다.deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
✔️ 여기서 자주 활용되는 메소드는 roatate 이다.
# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])
deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])
deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])
- rotate parmater가 1이면 1만큼 오른쪽으로 회전
- rotate parameter가 -1이면 1만큼 왼쪽으로 회전
