[프로그래머스] lv2-다리를 지나는 트럭(python)

 

코딩테스트 연습 - 다리를 지나는 트럭

TL;DR

• 큐(Queue)
• 구현(Implementation)

문제 요약

1. 모든 트럭이 다리를 건너러면 최소 몇 초가 필요한지 알아내는 프로그램을 작성해야 한다.
2. 다리는 수용할 수 있는 트럭의 수와 무게 제한이 있으며 제한을 넘지 않을 경우 트럭은 다리에 올라올 수 있다.

 

- 제한을 넘지 않으면서 트럭이 다리를 건널 수 있는 최소 수를 구하는 프로그램이다.

- 문제에 나온 조건들을 적절한 자료구조와 함께 구현해야 한다.

입출력 형태

[그림 1] 입출력 예시

 

예시 1 ::

다리에는 트럭이 2대 올라갈 수 있고, 무게는 10kg까지 견딘다. 이 때, 7, 4, 5, 6kg인 트럭이 지나는 최소의 수를 구하는 경우이다.

1초 시점에는 다리에 7kg 트럭이 올라온다.

2초 시점에는 4kg인 트럭이 다리에 올라올 수 없으므로 7kg 트럭이 다리의 중간을 지난다.

3초 시점에는 7kg 트럭이 나가서 4kg 트럭이 올라올 수 있다. 따라서 4kg 트럭이 올라온다.

4초 시점에는 4kg 트럭이 다리의 절반을 지나고 5kg 트럭이 올라와도 다리가 버틸 수 있으므로 5kg 트럭이 올라온다.

5초 시점에는 4kg 트럭이 나가고 5kg 트럭이 다리의 절반을 지나간다. 6kg 트럭은 올라올 수 없다.

6초 시점에는 5kg 트럭이 나가고 6kg 트럭이 올라온다.

7초 시점에는 6kg 트럭이 다리의 절반을 지나간다.

8초 시점에는 6kg 트럭이 다리를 나간다.

이런 과정을 통해 트럭이 지나간다. 다리의 길이가 2라면 트럭이 다리를 지나기 위해서는 2초가 필요하다.

풀이

문제 구현을 위해 1초가 흐를 때마다 일어나는 일들을 정리하면 다음과 같다.

1. 트럭이 하나 나간다. 해당 트럭의 무게만큼 다리 위 트럭의 무게 합이 감소한다.
2. 새로운 트럭이 다리에 들어올 수 있는지 확인한다. 만약 들어올 수 있다면 기존 트럭들이 이동한 빈 자리에 트럭이 들어간다. 다리 위 트럭의 무게 합이 새로운 트럭의 무게만큼 증가한다.
3. 새로운 트럭이 들어올 수 없다면 해당 자리는 빈 자리로 남아있다.

이렇게 3가지가 1초가 지날 때마다 반복된다. 이를 코드로 구현하면 아래와 같다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0 for _ in range(bridge_length)])
    truck_weights = deque(truck_weights)
    on_bridge_weight = 0
    
    # 트럭이 다리에 올라갈 때
    while bridge:
        answer += 1
        # 1. 기존 트럭이 나간다. 해당 무게를 제외해준다.
        on_bridge_weight -= bridge.popleft()
        
        if truck_weights:
            # 2. 트럭이 올라올 수 있는지 확인한다. 올라올 수 있는 경우 다리 위로 트럭을 올리고 무게를 증가시킨다.
            if on_bridge_weight + truck_weights[0] <= weight:
                truck = truck_weights.popleft()
                on_bridge_weight += truck
                bridge.append(truck)
            # 3. 트럭이 올라올 수 없는 경우는 해당 트럭의 자리를 빈 자리로 둔다.
            else:
                bridge.append(0)

    return answer

 

bridge 변수는 현재 다리에 올라와있는 트럭 현황을 나타내는 리스트이다. 0번째 인덱스부터 추출해야 하므로 모두 deque로 바꾸어 주었다. pop(0) 연산을 써도 문제를 해결할 수 있지만 시간이 훨씬 많이 걸리게 된다. on_bridge_weight는 현재 다리에 올라와있는 트럭들의 무게 합을 나타낸다. sum(bridge)를 사용할 경우에는 시간 초과가 떠서 문제를 풀 수 없는 테스트 케이스가 존재한다.

 

시간이 지나가면 우선 다리에 있는 트럭이 한 대 빠진다. 다리에서 트럭이 한 대 내렸으므로 해당 무게를 제거해준다.

그리고 트럭이 들어올 수 있는지 확인한다. 트럭의 무게와 현재 다리에 올라와있는 무게의 합이 weight를 넘지 않으면  해당 트럭을 트럭 목록에서 제거하고 다리에 올린다. 새로운 트럭이 올라왔으므로 다리의 무게도 갱신해준다.

만약 올라올 수 없다면 bridge에 0을 채워준다. 0으로 채워주는 이유는 트럭의 빈 자리를 표시하기 위해서이다. 만약 0이 채워지지 않는다면 계속해서 bridge에서는 pop이 일어나며 다리의 길이가 줄어들어 트럭들이 다리를 통과하기 위한 원래 길이보다 짧아지게 되어 정확한 시간을 구할 수 없다.

 

bridge가 빌 때까지 이 연산을 반복하면 트럭들이 1초에 한 번씩 이동하며 결과를 얻을 수 있다.