[큐/스택] 다리를 지나는 트럭 (Level 2)

1. 문제

2. 나의 풀이

2-1) 5번 케이스에서 시간초과나는 나의 코드

def solution(bridge_length, weight, truck_weights):
    in_bridge = []
    second = 0
    while truck_weights:
        second += 1
        if in_bridge and len(in_bridge) % bridge_length == 0:
            in_bridge.pop(0)
        temp = truck_weights.pop(0)
        in_bridge.append(temp)

        if sum(in_bridge) > weight:
            truck_weights.insert(0, temp)
            in_bridge.pop()
            in_bridge.append(0)

    return second+bridge_length

bridge_length = 2
weight = 1
truck_weights = [1,1]
print(solution(bridge_length, weight, truck_weights))

2-2) 드디어 통과한 나의 풀이

• sum(in_bridge) 대신에 sum을 수동적으로 추가해서 관리하는 방식으로 바꿈!
• sum(리스트)가 O(N)이라서 그만큼 시간이 오래걸렸나봄

def solution(bridge_length, weight, truck_weights):
    in_bridge = []
    second = 0
    sum = 0

    while truck_weights:
    # for i in range(3):
        second += 1

        if len(in_bridge) == bridge_length:
            sum -= in_bridge.pop(0)


        temp = truck_weights.pop(0)
        in_bridge.append(temp)
        sum += temp

        if sum > weight:
            truck_weights.insert(0, temp)
            in_bridge.pop()
            in_bridge.append(0)
            sum -= temp

        # print(sum, in_bridge)

    return second+bridge_length

3. 남의 풀이

Reference

4. 느낀 점

• 5번 케이스에서 시간초과!!!