[Python] 다리를 지나는 트럭

from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    truck_weights = deque(truck_weights)
    passing = deque([0] * bridge_length)
    time = 0
    bridge_w = 0
    
    while passing:
        time += 1
        move = passing.popleft()
        # 다리를 완전히 지나간 트럭이 있었을 경우(move = 다리를 빠져나간 트럭 / 일 경우)
        if move != 0 :
            bridge_w -= move
        
        if truck_weights:
            if bridge_w + truck_weights[0] <= weight:
                truck = truck_weights.popleft()
                passing.append(truck)
                bridge_w += truck
            else:
                passing.append(0)
    
    return time

---

풀이

list.pop(0)의 시간 복잡도는 O(N)이고, deque.popleft()의 시간 복잡도는 O(1)이므로 deque를 이용한다.

 

1. 다리의 길이만큼 deque을 만들어주고(passing), while문을 돌때마다 시간이 추가되고  트럭도 한 칸씩 앞으로 옮겨가는 형식의 코드이다.
2. 한 칸씩 옮겼을 때, 만약 다리를 완전히 지나간 트럭이 있었을 경우, (move = passing.popleft() 를 했는데, move가 0이 아닐 경우) 그 트럭의 무게를 현재 다리의 무게(bridge_w)에서 빼준다.
3. 그리고 다음 차례의 트럭이 다리를 지나가도 된다면, (현재 지나가고 있는 트럭들의 무게 합 + 다음 차례 트럭 무게 <= 다리 무게) 대기하고 있는 트럭 deque(truck_weights)에서 뽑아와, 지나가고 있는 트럭 deque(passing)에 넣어주고 현재 다리의 무게에 트럭의 무게를 더한다.
4. 다음 차례의 트럭이 지나가지 못한다면, 트럭을 한 칸씩 앞으로 옮기기만 하는 형태의 코드이다.

---

처음 풀이는 이와 같았으나, 시간 초과에 걸렸다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    truck_weights = deque(truck_weights)
    passing = deque([0] * bridge_length)
    time = 0
    
    while passing:
        time += 1
        move = passing.popleft()
        
        if truck_weights:
            if sum(passing) + truck_weights[0] <= weight:
                passing.append(truck_weights.popleft())
            else:
                passing.append(0)
    
    return time

다리를 지나는 트럭들의 무게 합을 구하는 부분을  일일이 더하거나 빼지 않고 sum함수를 활용해 풀었는데, 코드는 간결하나 시간이 오래걸린다는 단점이 있었다. 그리고 deque를 이용하면 더 시간이 걸려 list.pop(0)을 활용해야 통과되었다.