프로그래머스 Lv2 다리를 지나는 트럭

문제

링크

풀이

1. list, sum 사용

def solution(bridge_length, weight, truck_weights):
    start = len(truck_weights)
    bridge = [0] * bridge_length
    end = []
    time = 0
    while len(end) != start : 
        b = bridge.pop(0)
        if b > 0 :
            end.append(b)
        if not truck_weights or sum(bridge) + truck_weights[0] > weight :
            bridge.append(0)
        else :
            bridge.append(truck_weights.pop(0))
        time += 1
    return time     

위 코드를 돌렸더니 아래처럼 모든 테스트 케이스를 통과헀지만, 시간이 너무 오래 걸렸다.

혹시나 해서 deque를 써봤지만, 오히려 시간 초과가 발생했다.
프로그래머스에서 다른 분들의 코드를 보던 중, 어떤 분이 sum 대신 변수를 사용하면 더 빨라진다고 하셨다.
sum(bridge)를 사용하지 않고 add라는 변수를 추가했더니 아래와 같이 속도가 엄청 빨라진 모습을 확인할 수 있다.

2. list, 변수 사용

def solution(bridge_length, weight, truck_weights):
    start = len(truck_weights)
    bridge = [0] * bridge_length
    weight_on_bridge = 0
    end = []
    time = 0
    while len(end) != start : 
        b = bridge.pop(0)
        weight_on_bridge -= b
        if b > 0 :
            end.append(b)
        if not truck_weights or weight_on_bridge + truck_weights[0] > weight :
            bridge.append(0)
        else :
            t = truck_weights.pop(0)
            bridge.append(t)
            weight_on_bridge += t
        time += 1
    return time     

bridge_length는 최대 10,000인데 계속해서 sum을 하는 것보다 다른 변수를 통해 하나씩 더하고 빼는 방법이 더 빠르기 때문에 위와 같이 빨라졌다.

3. deque, 변수 사용

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque([0] * bridge_length)
    add = 0
    end = deque()
    truck = deque(truck_weights)
    time = 0
    while len(end) != len(truck_weights) : 
        b = bridge.popleft()
        add -= b
        if b > 0 :
            end.append(b)
        if not truck or add + truck[0] > weight :
            bridge.append(0)
        else :
            t = truck.popleft()
            add += t
            bridge.append(t)
        time += 1
    return time

list를 사용했던 코드에서 변수를 사용했어야 했는데, deque를 사용한 것을 모르고 변수를 사용했다. 그랬더니 이상하게 list + 변수보다 deque + 변수가 훨씬 빠른 모습을 볼 수 있다.
deque에서는 시간초과가 났었는데 변수를 사용했다고 이렇게 빨라질 수가 있나???
의문이다