Programmers Lv.2 다리를 지나는 트럭

📚 문제 설명

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

📖 문제 풀이

Code_1 - 런타임 에러

from collections import deque
def solution(bridge_length, weight, truck_weights):
    t = 0
    crossed = []
    bridge = [0]*bridge_length
    n = len(truck_weights)
    while len(crossed) < n:
        t += 1
        truck = bridge.pop(0)
        if truck != 0: # 다리를 건넌 트럭이 존재하는 경우
            crossed.append(truck)
        if len(truck_weights) > 0:
            if sum(bridge) + truck_weights[0] <= weight: # 현재 다리를 건너는 트럭의 무게와 새 트럭의 합이 weight보다 작은 경우
                bridge.append(truck_weights.pop(0))
            else:
                bridge.append(0)
    return t

• 매 반복문마다 sum()을 사용해서 그런지 5번 테스트케이스에서 런타임 에러가 발생함
• 이를 해결하고자 bridge내의 트럭 무게를 s 변수에 저장하고 다리에 추가되는 경우 truck_weights의 첫 요소를 더하고, 다리를 건너는 경우 truck_weights의 첫 요소를 빼는 방식으로 구현함

Code_2 - 성공

from collections import deque
def solution(bridge_length, weight, truck_weights):
    t, s = 1, 0
    crossed = []
    bridge = deque([0]*(bridge_length-1))
    while truck_weights:
        s += truck_weights[0]
        if s <= weight:
            bridge.append(truck_weights.pop(0))
        else:
            s -= truck_weights[0]
            bridge.append(0)
        s -= bridge.popleft()
        t += 1
    return t + len(bridge)