[Python] 프로그래머스 - 다리를 지나는 트럭

문제

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

트럭 무게가 담겨 있는 리스트, 다리의 길이, 다리가 버틸 수 있는 무게가 주어졌을 때 모든 트럭이 건너는 데 걸리는 시간을 계산하는 문제입니다. 트럭은 리스트에 주어진 순서대로 다리를 건너야 하며, 한 트럭이 다리를 올랐다면 1초후에 다음트럭이 올라가는 식으로 계산합니다.

풀이

문제에서 리스트를 직접 제공해주고 있기도 해서, 간단하게 for문을 통해서 해결을 시도해봤는데요! 이렇게 하면 다리위에 올라가 있는 트럭중 한대가 내려와 다른 트럭이 올라갈 수 있는 경우를 계산하지 못하게 되네요. 예시로 주어진 테스트 케이스는 모두 통과하지만 실행하면 몇가지 테스트 케이스에서 실패하게 됩니다.

1. 배열의 첫번째 요소를 더하고 시작합니다. 다음 트럭이 올라올 시간까지 미리 계산하여 1초를 더해줍니다.
2. 현재 트럭이 이전에 올라간 트럭과 더했을 때 다리가 견딜 수 있는 무게라면 1초만 더해줍니다. (트럭이 올라오는 시간 1초)
3. 아니라면 트럭이 건너는 시간을 추가해줍니다.

def solution(bridge_length, weight, truck_weights):
    count = bridge_length + 1
    
    for i in range(1,len(truck_weights)):
        if ( weight >= truck_weights[i-1] + truck_weights[i]):
            count += 1
            continue
        count += bridge_length
        
    return count

글로 써놓고 보니 놓친 부분이 많다는 것을 깨닫게 되네요..ㅎㅎ 다리위의 상태를 계속해서 추적해야하고, 경과시간도 추적하여 계산해주어여 합니다. 따라서 큐를 사용한 방식으로 해결해보았습니다.

1. truck_weighs 리스트를 순회합니다.
2. 트럭이 올라갈 떄 마다 1초씩 추가합니다.
3. 다리의 맨 앞에 있는 트럭은 pop을 통해서 탈출합니다. 탈출한 트럭의 무게만큼 다리위의 무게도 제거해줍니다.
4. 새로운 트럭을 올릴 수 있는 지 여부를 if문을 통해 판별합니다. 만약 올릴 수 있다면 다리에 트럭 하나를 추가하고 다리위의 무게에 트럭의 무게를 추가합니다.
5. 아니라면 0을 추가하여 트럭 사이의 간격을 유지하도록 합니다.
6. 마지막 트럭이 다리를 완전히 건너는 시간까지 추가하여 결과를 반환합니다.

Python

def solution(bridge_length, weight, truck_weights):
    count = 0
    bridge = [0] * bridge_length
    total_weight = 0 

    for truck in truck_weights:
        while True:
            count += 1
            exited_truck = bridge.pop(0)
            total_weight -= exited_truck

            if total_weight + truck <= weight:
                bridge.append(truck)
                total_weight += truck
                break
            else:
                bridge.append(0)
    count += bridge_length

    return count

 

제출된 다른 코드를 둘러봤을 때 다리 객체를 만들어 트럭의 동작을 구현한 방법도 있어서 리뷰해보겠습니다. 빠르다는 의견이 꽤 보였는데 위에 작성한 코드랑 둘 다 O(n)이고 개인적으로 위의 코드가 더 이해하기 쉽지 않나 하는 생각이 있습니다. 결과적으로 두 코드 모두 동작 방식이 크게 다르지 않기 떄문에요 ㅎㅎ

1. Bridge 클래스를 통해서 다리의 상태와 트럭들이 다리 위에 있을 때 동작을 작성합니다.
2. push → 트럭 올리기 pop → 트럭 빼기
3. Solution으로 돌아와서 다리 객체의 트럭들을 큐로 관리합니다.
4. 다리 객체를 생성하여 다리 길이와 최대 무게를 저장합니다.
5. 다리가 비어있는 상태를 표현하기 위해 DUMMY_TRUCK으로 다리에 0을 채워 넣습니다.
6. 다리의 맨 앞 트럭을 다리에서 제외하고 다음 트럭이 올라올 수 있는 지 여부를 판단합니다.
7. 올라갈수 있다면면 트럭 큐에서 해당 트럭을 제거하고, 없다면 0을 채워넣습니다.
8. 트럭이 올라가는 시간 1초를 추가합니다
9. 5-7을 반복하고 다리에서 트럭들을 빼내면서 시간을 추가합니다.

import collections

DUMMY_TRUCK = 0


class Bridge(object):

    def __init__(self, length, weight):
        self._max_length = length
        self._max_weight = weight
        self._queue = collections.deque()
        self._current_weight = 0

    def push(self, truck):
        next_weight = self._current_weight + truck
        if next_weight <= self._max_weight and len(self._queue) < self._max_length:
            self._queue.append(truck)
            self._current_weight = next_weight
            return True
        else:
            return False

    def pop(self):
        item = self._queue.popleft()
        self._current_weight -= item
        return item

    def __len__(self):
        return len(self._queue)

    def __repr__(self):
        return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))


def solution(bridge_length, weight, truck_weights):
    bridge = Bridge(bridge_length, weight)
    trucks = collections.deque(w for w in truck_weights)

    for _ in range(bridge_length):
        bridge.push(DUMMY_TRUCK)

    count = 0
    while trucks:
        bridge.pop()

        if bridge.push(trucks[0]):
            trucks.popleft()
        else:
            bridge.push(DUMMY_TRUCK)

        count += 1

    while bridge:
        bridge.pop()
        count += 1

    return count


def main():
    print(solution(2, 10, [7, 4, 5, 6]), 8)
    print(solution(100, 100, [10]), 101)
    print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)


if __name__ == '__main__':
    main()