Lv2. 다리를 지나는 트럭

# 문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 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 이하입니다.

# 입출력 예

문제 해결 시 고려사항

• 다리를 건너는 트럭들에 대한 삽입, 삭제 조건 고려

본 문제는 여러 무게로 구성된 대기 중인 모든 트럭들이 무게 제한이 있는 다리를 건너도록 하고 그에 소요되는 최소의 시간을 구하는 문제이다. 문제를 해결함에 있어 고려할 점은 대기 중인 트럭이 다리에 진입할 수 있는지와 다리를 지나는 트럭이 다리를 언제 빠져나가는지이다.

먼저 대기 중인 트럭이 다리에 진입할 수 있는지 여부에 대한 판단 조건을 생각해보자.

트럭이 지나는 다리는 weight라는 변수로 주어진다. 만약 다리를 지나는 트럭이 없다면 대기 중인 트럭 중 제일 앞의 트럭의 무게가 weight 이하이면 진입 가능하다. 하지만 만약 다리를 지나는 트럭이 존재한다면 다리 위에 존재하는 모든 트럭의 무게와 새로 진입할 트럭의 무게의 합이 weight보다 작은지를 검사해야 한다.

 # 대기 중인 트럭이 존재하고 현재 다리 위 트럭과 대기 트럭 중 제일 앞의 트럭의 무게가 제한 무게보다 작다면
         if truck_weights and summ(passing) + truck_weights[0] <= weight:
             # passing 큐에 대기 트럭 중 가장 앞 트럭을 배치
             passing.append([truck_weights.popleft(),0])

이번에는 다리를 지나는 트럭이 다리를 언제 빠져나갈 수 있는지 여부에 대한 판단 조건을 생각해보자.

문제에서, 모든 트럭은 1초에 1만큼 움직인다고 주어졌으며 다리의 길이 bridge_length 또한 주어졌다. 따라서 트럭이 다리위에 존재했던 시간이 bridge_length가 된다면 다리를 지난 것이라고 판단할 수 있다.

 # 건너는 트럭의 지난 시간 1초씩 추가
         for i in passing:
             i[1] += 1
         # 다리를 건너는 트럭 중 지난 시간이 bridge_length와 같은 트럭이 있으면 passed로 이동
         if passing : 
             if passing[0][1] == bridge_length:
                 passed.append(passing.popleft())
         # 모든 트럭이 다리를 건너면 반복 종료
         if len(passed) == total:
             break      

passed 내 원소의 수가 초기 truck_weights 원소의 수와 같아지면 모든 트럭이 다리를 건넌 것이기 때문에 반복을 종료하고 정답(최소 소요시간)을 반환한다.

전체 코드

from collections import deque

def summ(li):
    result = 0
    for i in li:
        result += i[0]
    return result

def solution(bridge_length, weight, truck_weights):
    answer = 1
    # 주어진 트럭의 수
    total = len(truck_weights)
    # 대기 트럭을 큐로 관리하기 위해 deque() 활용
    truck_weights = deque(truck_weights)
    # 지나간 트럭을 담을 리스트
    passed = []
    # 다리를 건너는 트럭을 담을 큐
    passing = deque()
    # 초기 passing 세팅([첫 트럭, 지난 시간])
    passing.append([truck_weights.popleft(), 1])   
    while True:
        answer += 1
        # 대기 중인 트럭이 존재하고 현재 다리 위 트럭과 대기 트럭 중 제일 앞의 트럭의 무게가 제한 무게보다 작다면
        if truck_weights and summ(passing) + truck_weights[0] <= weight:
            # passing 큐에 대기 트럭 중 가장 앞 트럭을 배치
            passing.append([truck_weights.popleft(),0])
        # 건너는 트럭의 지난 시간 1초씩 추가
        for i in passing:
            i[1] += 1
        # 다리를 건너는 트럭 중 지난 시간이 bridge_length와 같은 트럭이 있으면 passed로 이동
        if passing : 
            if passing[0][1] == bridge_length:
                passed.append(passing.popleft())
        # 모든 트럭이 다리를 건너면 반복 종료
        if len(passed) == total:
            break      
    return answer+1