[Algorithm] [Python] Programmers - 다리를 지나는 트럭

Programmers - 다리를 지나는 트럭

 

문제 설명

---

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

 

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

 

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

 

 

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

 

제출 코드

---

Python

 

1차 제출 코드

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    answer = 0
    bridge = deque([0 for _ in range(bridge_length)])
    truck_weights = deque(truck_weights)

    while bridge:
        bridge.popleft()
        answer += 1
        if truck_weights:
            if sum(bridge) + truck_weights[0] <= weight:
                bridge.append(truck_weights.popleft())
            else:
                bridge.append(0)
    return answer

 

하나의 테스트케이스에서 시간 초과가 떳다.

 

질문 내역을 살펴보다가 sum(bridge) 부분은 sum 함수 없이 관리가 가능할 것 같아 아래 코드로 변경하였다.

 

최종 제출 코드

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    answer = 0
    bridge = deque([0] * bridge_length)                
    truck_weights = deque(truck_weights)                    
    bridge_weight = sum(bridge)

    while bridge:
        bridge_weight -= bridge[0]
        bridge.popleft()
        answer += 1
        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                bridge_weight += truck_weights[0]
                bridge.append(truck_weights.popleft())
            else:
                bridge.append(0)
    return answer

sum()은 O(N)의 복잡도를 갖기 때문에 해당 함수 사용을 지양하고 bridge 의 총합을 별개로 관리했더니 Accept 되었다.

 

Swift

 

1차 제출 코드

import Foundation

func solution(_ bridge_length: Int, _ weight: Int, _ truck_weights:[Int]) -> Int {
    var answer = 0
    var bridge = Array(repeating: 0, count: bridge_length)
    var truck_weights = truck_weights

    while bridge.count != 0 {
        bridge.removeFirst()
        answer += 1

        if truck_weights.count != 0 {
            if bridge.reduce(0, +) + truck_weights[0] <= weight {
                bridge.append(truck_weights.removeFirst())
            } else {
                bridge.append(0)
            }
        }
    }

    return answer
}

위 코드는 세 개의 테스트케이스에서 시간 초과가 떳다.

 

파이썬 코드의 sum 부분을 변경한 것과 같이 reduce 부분을 변경하였다.

 

최종 제출 코드

func solution(_ bridge_length: Int, _ weight: Int, _ truck_weights:[Int]) -> Int {
    var answer = 0
    var bridge = Array(repeating: 0, count: bridge_length)
    var truck_weights = truck_weights
    var bridge_weight = bridge.reduce(0, +)

    while bridge.count != 0 {
        bridge_weight -= bridge[0]
        bridge.removeFirst()
        answer += 1

        if truck_weights.count != 0 {
            if bridge_weight + truck_weights[0] <= weight {
                bridge_weight += truck_weights[0]
                bridge.append(truck_weights.removeFirst())
            } else {
                bridge.append(0)
            }
        }
    }

    return answer
}

 

문제 풀이

---

bridge : 현재 다리의 상황을 확인하기 위한 변수

 

위 문제는 주어진 트럭들이 모두 다리를 지나는데 걸리는 시간을 요구한다.

 

따라서, bridge 가 빌 때 까지 반복하며 while 문 1회 반복을 1초로 카운팅한다.

 

또한, 앞 쪽에 위치하는 트럭이 우선적으로 다리를 건너야 하기 때문에 FIFO 성질을 갖는 자료구조가 해당 문제를 풀기에 적절하다.

 

truck_weights 와 bridge 리스트에서 0번쨰 원소의 값을 pop 해야 하기 때문에 효율성을 고려하여 파이썬에서는

deque를 활용하였다.

 

리스트의 내장 함수 pop(0)은 O(N)의 시간복잡도를 가지며 deque의 내장 함수 popleft()는 O(1)의 시간복잡도를 갖기에 훨씬 효율적이다.

 

1초가 지날 때 마다 현재 다리에 있는 트럭의 무게와 다음으로 올라갈 차례의 무게의 합이 다리가 버틸 수 있는 최대 하중을 넘는지 확인한다.

 

만일 두 대 이상의 트럭이 동시에 트럭을 건널 수 있다면 다음 차례의 트럭 또한 다리를 건너도록 한다.

 

그 외의 경우에는 0을 추가하여 다리를 왼쪽으로 밀어낸다.