[프로그래머스] 다리를 지나는 트럭 (python)

문제 설명

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

 

1. 트럭 여러 대가 일차선 다리를 지난다. 

2. 다리 위에 bridge_length만큼의 트럭만 올라갈 수 있으며, 다리 위의 트럭의 총 무게 합이 weigth를 넘으면 안된다. 

3. 하나의 트럭이 다리를 건너는데에는 bridge_length초가 걸린다.

4. 이때, 모든 트럭이 다리를 건너는데에 걸리는 최소 시간을 구하는 문제이다. 

 

접근

먼저 큐에 bridge_length만큼 0을 넣어주고, 다리 위의 트럭 수와 트럭의 총 무게합을 고려했을 때 조건에 부합한다면 트럭을 다리 위에 올리고 그렇지 않다면 0을 넣어주어 마지막 트럭이 다리를 건넜을 때까지의 시간을 반환해주려 했다. 

하지만 이렇게 되면 시간복잡도가 O(N)이 되기 때문에 다른 방법을 생각해봤다. 

문제를 다시 읽고 나니 마지막 트럭이 다리를 모두 건너는 시간만 알면 위 방법처럼 모든 값을 큐에 넣고 뺄 필요가 없다는 것이 보였다.

 

풀이

트럭이 처음 다리 위에 올라왔을 때, 트럭이 다리를 모두 건넜을 때의 시간을 큐에 넣어주었다. (현재 시간 + 다리길이)

다리 위의 가장 왼쪽에 있는 트럭의 끝나는 시간값이 현재 시간과 같다면 다리 위의 무게에서 트럭의 무게를 빼주고 다리 큐에서 삭제해주었다. 

마지막 트럭이 큐에 들어갔다면 반복문을 끝내고 마지막 트럭의 (끝나는 시간 +1)을 반환했다. 

 

코드 

from collections import deque


def solution(bridge_length, weight, truck_weights):
    bridge = deque([])
    trucks = len(truck_weights)

    sec, idx = 0, 0
    while idx < trucks:
        if len(bridge) > 0 and bridge[0][1] == sec:
            weight += bridge[0][0]
            bridge.popleft()

        if weight - truck_weights[idx] >= 0:
            bridge.append((truck_weights[idx], sec + bridge_length))
            weight -= truck_weights[idx]
            idx += 1
        sec += 1

    return bridge[-1][1] + 1