프로그래머스 LV2 다리를 지나는 트럭

 

다리를 지나는 트럭

 

문제 설명 & 조건 확인

문제 설명

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

 

제한 조건

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

 

입출력 예

bridge_length	weight	truck_weights
2	10	[7,4,5,6]

 

 

핵심 아이디어

1. 다리 위 상태 관리

 - 큐를 활용해 (트럭 무게, 남은 시간) 형태로 저장

 

2. 매 tick 마다 트럭 이동

- 남은 시간 0인 트럭 제거

 

3. 새로운 트럭 추가

다리 현재 무게, 최대 무게 조건을 사용해 새로운 트럭을 다리에 추가

 

 

코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    tick = 0
    bridge = deque()
    bridge_weight = 0
    
    i = 0
    while i < len(truck_weights) or bridge:
        
        tick += 1
        
        if bridge and bridge[0][1] == 0:
            truck = bridge.popleft()
            bridge_weight -= truck[0]
            
        if i < len(truck_weights):
            if bridge_weight + truck_weights[i] <= weight and len(bridge) < bridge_length:
                bridge.append((truck_weights[i], bridge_length))
                bridge_weight += truck_weights[i]

                i += 1

        bridge = deque((w, t-1) for w, t in bridge)
    
    
    return tick

 

 

 

핵심 아이디어 구현 부분

- 다리 위 상태 관리 & 트럭 이동

bridge = deque((w, t-1) for w, t in bridge)

 

매 tick 마다 트럭이 이동한다.

 

- 남은 시간 0인 트럭 제거

if bridge and bridge[0][1] == 0:
    truck = bridge.popleft()
    bridge_weight -= truck[0]

 

이동이 끝난 트럭(남은 시간 0)인 트럭을 제거한다. 이때, bridge_weight에서 트럭의 무게도 함께 뺀다.

 

- 새로운 트럭 추가

if i < len(truck_weights):
    if bridge_weight + truck_weights[i] <= weight and len(bridge) < bridge_length:
        bridge.append((truck_weights[i], bridge_length))
        bridge_weight += truck_weights[i]

        i += 1

 

아직 대기중인 트럭이 존재할 때, 다리 무게와 새로운 트럭의 무게, 문제의 길이 조건을 같이 검사한 후 적합하다면 추가한다. 

 

 

Test Case

입력	출력
2, 10, [7, 4, 5, 6]	8
100, 100, [10]	101
100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]	110