9. 다리를 지나는 트럭 ★ (스택/큐, sum함수의 시간 복잡도, deque)

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0 for i in range(bridge_length)]
    success = []
    truckcnt = len(truck_weights)
    while True:
        #종료 조건 설정 
        if len(success) == truckcnt:
            break
        if bridge:
            if bridge[0] == 0:
                del bridge[0]
            else:
                success.append(bridge.pop(0))
        if truck_weights and truck_weights[0] + sum(bridge) <= weight and len(bridge) + 1 <= bridge_length:
            bridge.append(truck_weights.pop(0))
        else:
            bridge.append(0)
        answer += 1
    return answer

 

5번 tc에서 시간 초과 발생. 

 

 

원인은 sum 함수를 사용해서 + 시간 복잡도가 큰 pop을 사용해서. del을 대신 사용하였다. 

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0 for i in range(bridge_length)]
    bweight = 0
    success = []
    truckcnt = len(truck_weights)
    while True:
        #종료 조건 설정 
        if len(success) == truckcnt:
            break
        if bridge:
            if bridge[0] == 0:
                del bridge[0]
            else:
                success.append(bridge[0])
                bweight -= bridge[0]
                del bridge[0]
        if truck_weights and truck_weights[0] + bweight <= weight and len(bridge) + 1 <= bridge_length:
            bweight += truck_weights[0]
            bridge.append(truck_weights[0])
            del truck_weights[0]
        else:
            bridge.append(0)
        answer += 1
    return answer

 

bweight 변수를 지정해 새롭게 누적하는 방식으로 bridge의 무게를 측정하도록 하였더니

시간 초과가 해결되었다.

생각보다 sum 함수와 pop의 시간 복잡도는 높구나.. 

 

 

deque를 사용해서도 풀이해보았다. 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0 for i in range(bridge_length)])
    bweight = 0
    success = deque()
    truckcnt = len(truck_weights)
    truck_weights = deque(truck_weights)
    while True:
        #종료 조건 설정 
        if len(success) == truckcnt:
            break
        if bridge:
            if bridge[0] == 0:
                bridge.popleft()
            else:
                bweight -= bridge[0]
                success.append(bridge.popleft())
        if truck_weights and truck_weights[0] + bweight <= weight and len(bridge) + 1 <= bridge_length:
            bweight += truck_weights[0]
            bridge.append(truck_weights.popleft())
        else:
            bridge.append(0)
        answer += 1
    return answer