문제 설명

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

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

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
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]		[]				[]

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

입출력 예

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을 다리의 길이만큼 채워 준 뒤 매 차례마다 가장 앞의 원소를 pop하고 다음 차례의 트럭을 다리 위에 올리는 방식으로 접근하였다. 이때 pop한 원소가 0이 아닐 경우에 도착한 트럭 리스트에 추가해주고, 다음 차례의 트럭을 올리기 전에 다리 위의 모든 트럭과 다음 차례의 트럭의 무게 합이 제한 무게보다 낮을 때에만 올리도록 한다. 성능을 높이기 위해 전체 무게의 합은 그때 그때 구하는 것 대신 변수에 저장하여 관리하도록 하였다.

• 정답을 저장할 변수 answer를 0으로 선언한다.
• 다리 위의 트럭을 담을 큐 on_bridge를 0을 다리의 길이만큼 채워 deque로 선언한다.
• 트럭 리스트 truck_weights를 성능을 위해 deque로 재선언한다.
• l에 truck_weights의 길이를 저장한다.
• 도착한 트럭을 담을 리스트 arrived를 선언한다.
• 다리 위의 트럭의 전체 무게를 저장할 변수 total을 0으로 선언한다.
• arrived의 길이가 l보다 작을 동안 반복하는 while문을 돌린다.
  -> answer를 1 증가시킨다.
  -> on_bridge.popleft()의 값을 임시 변수 top에 저장한다.
  -> total에서 top을 뺴준다.
  -> 만약 top이 0보다 클 경우,
  --> arrived에 top을 넣어준다.
  -> 만약 truct_weights가 존재할 경우,
  --> 만약 total+truck_weights[0]이 weight보다 작거나 같을 경우,
  ---> 임시 변수 tmp에 truck_weights.popleft()의 값을 저장한다.
  ---> on_bridge에 tmp를 넣는다.
  ---> total에 tmp를 더한다.
  --> 그 외의 경우, on_bridge에 0을 넣는다.
• answer를 반환한다.

solution.py

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    on_bridge=deque([0]*bridge_length)
    truck_weights=deque(truck_weights)
    l=len(truck_weights)
    arrived=[]
    total=0
    while len(arrived)<l:
        answer+=1
        top=on_bridge.popleft()
        total-=top
        if top>0:
            arrived.append(top)
        if truck_weights:
            if total+truck_weights[0]<=weight:
                tmp=truck_weights.popleft()
                on_bridge.append(tmp)
                total+=tmp
            else:
                on_bridge.append(0)
    return answer