차가 들어오고 나가는 Bridge - 큐 구조로 와닿음. 큐로 풀어보자.

구현 자체는 특별한 알고리즘 없이,
1. truck_weights 큐 생성
2. bridge 위 트럭들의 무게를 나타낼 bridge 큐 생성
3. 다리 위에 못올라간 트럭이 없을 때 까지 다음을 반복
(truck_weights 큐에 하나 이상의 원소가 있는 동안, while truck_weights)

• 다리에 올릴 수 있다면 truck_weight append
• 다리에 올릴 수 없다면 0 append

Trial 1 - TC 5번 시간초과

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    answer = 0
    bridge = deque([0 for _ in range(bridge_length)])
    truck_weights = deque(truck_weights)
    while truck_weights:
        answer += 1
        
        bridge.popleft()
        newtruck = truck_weights[0]
        if sum(bridge) + newtruck <= weight:
            truck_weights.popleft()
            bridge.append(newtruck)
        else:
            bridge.append(0)
            
    answer += bridge_length    
    return answer

while문 안에 sum까지 있어서 O(n^2).

iteration마다 bridge 큐에서 하나 빼고 하나 더하는 식. 그정도는 내가 따로 관리해도 되지 않을까?

sum()을 매번 할 필요 없이, 그때그때 계산해서 변수 하나로 관리하는 걸로 개선해보자!

Trial 2 - 시간 개선

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    answer = 0
    bridge = deque([0 for _ in range(bridge_length)])
    truck_weights = deque(truck_weights)
    totalweight = 0
    while truck_weights:
        answer += 1
        
        totalweight -= bridge.popleft()
        newtruck = truck_weights[0]
        if totalweight + newtruck <= weight:
            truck_weights.popleft()
            bridge.append(newtruck)
            totalweight += newtruck
        else:
            bridge.append(0)
            
    answer += bridge_length    
    return answer