[level 2] 다리를 건너는 트럭

1. 문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

2. 문제 풀이

대기 트럭(truck_weights)과 다리를 건너는 트럭(in_bridge) 큐에 원소가 있는 동안 반복한다.

• time에 +1을 한다
• 만약 in_bridge에 원소가 있고, in_birdge의 0번째 원소의 1이 time과 같다면
  • 0번째 원소를 큐에서 빼고
  • 0번째 원소의 무게를 트럭의 총 합 무게에서 뺀다
• 만약 truck_weights에 원소가 있고, 트럭의 총 합 무게에 truck_weights[0]을 더한 값이 weight보다 작다면
  • truck_weights의 첫번째 원소를 뺀다
  • 해당 값을 트럭의 총 합 무게에 더한다
  • (트럭의 무게, 트럭이 다리를 완전히 건너는 시점)을 다리를 건너는 트럭(in_bridge) 큐에 추가한다. 

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0 
    truck_weights = deque(truck_weights)
    in_bridge = deque()
    sum_weight = 0 
    time = 0
    
    while truck_weights or in_bridge:

        time += 1
        
        if in_bridge and in_bridge[0][1] == time: 
            finish, _ = in_bridge.popleft()
            sum_weight -= finish 
        
        if  truck_weights and weight >= truck_weights[0] + sum_weight:
            truck = truck_weights.popleft()
            sum_weight += truck
            in_bridge.append((truck, time+bridge_length)) 
    
    
    return time

 

1) <다리를 건너는 트럭의 큐> 와 < 대기 트럭 큐> 로 나누어서 생각

2) 트럭이 다리를 완전히 건너는 시간을 어떻게 체크할 것인가? 

 

이 두 가지가 중요했던 문제였다.