[PS] 덱(Deque)

deque는 양쪽 끝에서 O(1)으로 삽입/삭제가 가능한 자료구조이다. 내부적으로 이중 연결 리스트 기반으로 구현되어 있다. 반면에 인덱스로 접근하면 O(n)이다. 그래서 인덱스 접근이 잦다면 list가 더 유리하다.

주요 메서드

메서드	설명	시간복잡도
`append(x)`	오른쪽 끝에 추가	O(1)
`appendleft(x)`	왼쪽 끝에 추가	O(1)
`pop()`	오른쪽 끝 제거 & 반환	O(1)
`popleft()`	왼쪽 끝 제거 & 반환	O(1)
`extend(iterable)`	오른쪽에 iterable 추가	O(k)
`extendleft(iterable)`	왼쪽에 iterable 추가 (역순)	O(k)
`rotate(n)`	n만큼 회전 (양수=오른쪽, 음수=왼쪽)	O(n)
`clear()`	모든 원소 제거	O(1)
`copy()`	얕은 복사본 반환	O(n)
`count(x)`	x의 등장 횟수 반환	O(n)
`insert(i, x)`	i번째 위치에 x 삽입	O(n) ⚠️
`remove(x)`	왼쪽부터 처음 등장하는 x 제거	O(n)
`reverse()`	제자리에서 순서 뒤집기 (반환값 없음)	O(n)
`maxlen` 속성	최대 크기 제한 (초과 시 반대쪽 자동 제거)	-
`len(dq)`	크기	O(1)
`dq[i]`	인덱스 접근	O(n) ⚠️

중요한 것은 append(), appendleft(), pop(), popleft(), rotate()이다. maxlen, extend(), extendleft()도 기억해두면 좋다.

주요 사용 사례

큐/스택
슬라이딩 윈도우
양 끝의 삽입/삭제가 반복적으로 발생할 때

활용 패턴

1. BFS

from collections import deque

# Graph
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()  # list의 pop(0)은 O(n) → 반드시 deque 사용
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Array
def bfs(arr, start, end):
		n, m = len(arr), len(arr[0])
		visited = [[False] * m for _ in range(n)]
		
		sx, sy = start
		ex, ey = end
		
		queue = deque([(sx, sy, 0)])  # (행, 열, 거리)
		visited[sx][sy] = True
		
		dx = [1, -1, 0, 0]
		dy = [0, 0, 1, -1]
		
		while queue:
				x, y, dist = queue.popleft()
				
				if x == ex and y == ey:
						return dist
						
				for d in range(4):
						nx, ny = x + dx[d], y + dy[d]
						if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and arr[nx][ny] == 1:
								visited[nx][ny] = True
								queue.append((nx, ny, dist + 1))
								
		return -1

2. 슬라이딩 윈도우 최댓값

크기가 k인 윈도우를 이동하며 각 구간의 최댓값 구하기

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # 인덱스 저장, 값은 단조 감소 유지
    result = []

    for i, num in enumerate(nums):
        # 윈도우 밖으로 나간 인덱스 제거
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # 현재 값보다 작은 기존 원소 제거 (뒤에서부터)
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])  # 덱의 앞 = 현재 윈도우 최댓값

    return result

# 예: [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]

3. `rotate()`로 원형 큐 시뮬레이션

요세푸스 순열 등

from collections import deque

def josephus(n, k):
    dq = deque(range(1, n + 1))
    result = []

    while dq:
        dq.rotate(-(k - 1))   # k-1칸 왼쪽으로 회전
        result.append(dq.popleft())  # 앞에 온 원소 제거

    return result

# josephus(5, 2) → [2, 4, 1, 5, 3]

4. `maxlen`으로 최근 N개 유지

from collections import deque

# 최근 3개 데이터만 유지하는 윈도우
window = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    window.append(x)
    print(list(window))
# [1] → [1,2] → [1,2,3] → [2,3,4] → [3,4,5]
# 크기 초과 시 반대쪽(왼쪽)이 자동으로 제거됨