[python] 리스트 pop(0)과 dequeue popleft()의 성능차이

프로그래머스 알고리즘 고득점 kit - 스택/큐

 

1. python의 리스트 특성

- 리스트는 동적 배열(Daynamic Array)로 구현되어 있다.

- 리스트의 요소는 메모리 상에서 연속적으로 저장된다

- pop(0)을 호출하면 첫번째 요소를 제거 후 이후 나머지 모든 요소를 한 칸씩 앞으로 이동시켜야 한다

→ pop(0)의 시간 복잡도는 O(n)이다(리스트의 길이에 비례)

 

2. Deque의 특성

- Deque(Double-Ended Queue)는 양방향으로 데이터를 효율적으로 추가 및 제거할 수 있도록 설계된 자료구조이다.

- python의 collections.deque는 이중 연결 리스트로 구현되어 있다.

- popleft()를 호출하면 첫번째 노드 제거 후 포인터를 업데이트 한다

→ 다른 요소를 이동시키는 작업이 없으므로 O(1)의 시간복잡도를 가진다

 

3. 문제 풀이 비교 

(1) pop(0)로 풀기 성능 : 메모리: 10.2 MB, 시간: 267.21 ms  

def solution(bridge_length, weight, truck_weights):
    time = 0
    temp_w = 0
    bridge = [0] * bridge_length
    while truck_weights or temp_w:
        time += 1
        truck =bridge.pop(0)
        temp_w -= truck

        if truck_weights and (temp_w + truck_weights[0] <= weight):
            truck = truck_weights.pop(0)
            bridge.append(truck)
            temp_w += truck

        else:
            bridge.append(0)

    return time

 

(2) dequeue로 풀기 성능: 메모리: 10.1 MB, 시간: 53.60 ms

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge = deque([0] * bridge_length)  # 다리 길이만큼 초기화
    temp_w = 0  # 현재 다리 위 트럭 무게 합계

    while truck_weights or temp_w > 0:  # 대기 트럭이 있거나 다리 위에 트럭이 있는 동안 반복
        time += 1
        # 다리에서 트럭(또는 빈 공간) 제거
        temp_w -= bridge.popleft()

        if truck_weights and temp_w + truck_weights[0] <= weight:
            # 새로운 트럭 추가
            truck = truck_weights.pop(0)
            bridge.append(truck)
            temp_w += truck
        else:
            # 트럭이 못 올라오면 빈 공간 추가
            bridge.append(0)

    return time