[알고리즘 프로그래머스] 다리를 지나는 트럭 (LEVEL 2)

(문제) 다리를 지나는 트럭 [스택/큐]

---

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다.

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.

트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다.

무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다.

이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

입력설명

첫번째 입력으로는 bridge_length 가 입력이 되고, 두번째 입력으로는 weight가 입력 됩니다.

그리고 세번째 입력으로는 truck_weights가 입력이 됩니다.

bridge_length는 1 이상 10,000 이하입니다.

weight는 1 이상 10,000 이하입니다.

truck_weights의 길이는 1 이상 10,000 이하입니다.

모든 트럭의 무게는 1 이상 weight 이하입니다.

출력설명

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성

테스트케이스

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

---

해결방법

1. 각 트럭에 시간을 측정할 수 있는 숫자 추가
2. 다리를 건너고 있는 트럭을 정의할 수 있는 리스트 생성
3. 처음에 트럭을 다리를 건너고 있는 리스트에 삽입을 한다.
4. 추가 할 때, 다리의 무게를 비교할 수 있도록 무게 정보를 저장할 수 있는 변수 1개를 생성한다.
5. 만약 이 트럭이 삽입되고, 트럭의 무게가 만약 다음 트럭의 무게를 더했을 경우 작으면 1개 더 추가한다 이때 무게 또한 더한다, 만약 클 경우 추가하지 않는다.
6. 이때 다리를 건너고 있는 트럭에 있는 트럭들의 시간을 + 1 씩 해주면서 만약 다리의 길이가 시간과 같아질 경우 다리를 건너고 있는 트럭의 맨 앞에 있는 것을 뺀다. 이때 저장하고 있는 무게 변수에 트럭의 무게를 뺀다.
7. 만약 다리를 건너고 있는 트럭도 존재하지 않고, 대기 중인 트럭도 없을 경우 끝낸다.
8. 이 과정을 생 수 있는 count 변수를 만들어서 1바퀴 돌 때마다 + 1 해준다.

---

코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(list(a) for a in zip(truck_weights, [0] * len(truck_weights)))
    bridge = deque()
    
    bridge.append(truck_weights.popleft())
    
    # 초기화
    _sum = bridge[0][0]
    bridge[0][1] = 1
    count = 1
    
    while bridge or truck_weights:
        count = count + 1

        if bridge[0][1] == bridge_length:
            a = bridge.popleft()[0]
            _sum = _sum - a

        if truck_weights and _sum + truck_weights[0][0] <= weight:
            current = truck_weights.popleft()
            bridge.append(current)
            _sum = _sum + current[0]

        for i in range(len(bridge)):
            bridge[i][1] = bridge[i][1] + 1

    return count