[프로그래머스] 다리를 지나는 트럭 / 파이썬

문제 정리

---

https://programmers.co.kr/learn/courses/30/lessons/42583

다리에 올라갈 수 있는 트럭 수 bridge_length
다리가 견딜 수 있는 무게 weight
트럭 별 무게 truck_weights
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 반환하는 문제입니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

입출력 예

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

문제 풀이

---

큐를 이용해 접근했습니다.
빈 도로는 0으로 채워 표현하였고 도로의 원소가 없어질 때 까지 시간증가와 popleft()를 반복합니다.
이 때 다리에 있는 트럭의 무게와 들어올 트럭의 무게를 합한 것이 견딜 수 있는 무게보다 작은지 확인해서 작거나 같다면 트럭을 다리에 올리고 크다면 0을 append합니다.

시간초과

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0] * bridge_length)
    bridge_weight = 0
    while(bridge):
        time += 1
        bridge.popleft()
        if truck_weights:
            if sum(bridge) + truck_weights[0] <= weight:
                bridge.append(truck_weights.popleft())
            else:
                bridge.append(0)
    return time 

5번 테스트 케이스에서 시간초과가 낫습니다.
아무래도 다리에 있는 트럭의 무게를 구하기 위해 sum()을 사용했는데 시간복잡도가 O(n)이다 보니 도로의 길이가 길어질 경우 시간초과가 나는 것 같습니다.
따라서 sum을 사용하지 않고 별도의 변수 bridge_weight를 만들어 해결했습니다.

최종 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0] * bridge_length)
    bridge_weight = 0
    while(bridge):
        time += 1
        bridge_weight -= bridge.popleft()
        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                truck = truck_weights.popleft()
                bridge.append(truck)
                bridge_weight += truck
            else:
                bridge.append(0)
    return time