99클럽 코테 스터디 2일차 TIL / 다리를 지나는 트럭

다리를 지나는 트럭

시간 제한 : 10초(정확성 테스트만 존재)
학습 키워드 : 큐, 구현

문제 설명

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

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

제한 조건

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

from collections import deque
def solution(bridge_length, weight, truck_weights):
	#다리에 올라와 있는 트럭, 다리에 올라가기 전 트럭 명시
    truck_weights = deque(truck_weights)
    bridge = deque()
    current_weight = 0
    time = 0

	# 다리 위에 트럭이 있거나 아직 타지 않은 트럭이 있는 경우 반복해줌.
    while truck_weights or bridge:
    	#매 루프마다 시간을 더해주면서 진행상황 업데이트
        #bridge : list[[트럭의 무게, 다리에서 내려가는 시간]]
        time += 1
		#bridge 맨 앞의 트럭이 내려갈 시간이 됐을 때 popleft()로 빼줌
        if bridge and bridge[0][1] == time:
            current_weight -= bridge.popleft()[0]
        
        #트럭이 올라탈 수 있으면 truck_weights, bridge,current_weight의 진행상황 업데이트
        if truck_weights and current_weight + truck_weights[0] <= weight:
            truck = truck_weights.popleft()
            bridge.append((truck, time + bridge_length))
            current_weight += truck
    #루프 탈출하는 순간 바로 시간 리턴
    return time

코멘트

꽤 골머리를 앓았던 문제이다. 처음에 bridge에 시간 정보를 넣지 않고 풀려고 했는데 코드를 수정하는 과정에서 누더기가 되었고 그마저도 실패해서 조금 더 많은 정보(다리에 올라간 시간이나 다리에서 내려가는 시간 등)를 저장하고자 했다. 다리를 지나가는 문제(다리 말고도 여러 변형이 있겠지만) 에서는 다리위의 정보와 아직 올라가지 않은 목록들의 순서가 있기 때문에 deque부터 만들고 봐야겠다는 생각