[프로그래머스 고득점 Kit - 스택/큐] 5. 다리를 지나는 트럭

[프로그래머스 고득점 Kit] 다리를 지나는 트럭

 

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

입출력 예

---

[내 풀이]

- 32분 

- 트럭 길이가 일정하므로 트럭이 차지하는 칸을 리스트의 한 칸에 무게를 넣어  표현한다.

- bridge는 양쪽에서 입/출력이 일어나므로 deque

- truck_weights는 popleft() 를 사용하려고 deque를 썼지만, 사실 reverse 로 정렬한 다음 pop을 쓰는 게 더 간단했을 것 같다. 

- 매 cnt 마다 bridge의 제일 왼쪽 값은 고정적으로 빠져나간다. 

- 무게제한에 걸리지 않으면 새 트럭이 추가되고 bridge에 트럭 무게 값이 추가되며, 트럭만큼의 무게가 상승한다.

- 무게제한에 걸리면 새 트럭이 추가되지 못해 0이 추가 되며, 무게는 변하지 않는다.

- 대표 풀이에 비해 아쉬운 점: 나는 도착한 트럭의 개수를 세어 종료를 판단하려고 했다. 하지만 그럴 필요 없이, 기본 while 골격인 truck_weights가 비는 시점으로부터 bridge_length만큼을 더하면 종료 시점을 예측할 수 있다. 이 때문에 불필요한 조건을 일일이 계속 확인하게 되었다. (any(0!=x for x in bridge)라던가, if len(arrived)==truck cnt 라던가. 

- 그 외의 핵심 알고리즘은 대표 풀이와 같다. 

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0]*bridge_length)
    truck_weights = deque(truck_weights)
    truck_cnt = len(truck_weights)
        
    bridge_weight = 0
    arrived = []
    cnt = 0
    while truck_weights or any(0!=x for x in bridge):
        cnt += 1
        s = bridge.popleft()
        bridge_weight -= s
        if s!=0: arrived.append(s)
        if len(arrived)==truck_cnt: return cnt
        if truck_weights and bridge_weight+truck_weights[0]<=weight:
            now = truck_weights.popleft()
            bridge.append(now)
            bridge_weight += now
        else:
            bridge.append(0)
            
    return answer

 

 

---

[대표 풀이]

- 리스트를 reverse 해서 pop() 효율을 높이는 방법, 한 쪽으로만 값이 나오는 경우 그냥 stk 인 채로 pop만 사용해도 된다.

- 트럭이 다리 위에 올라간 후 다리 길이만큼의 시간이 소요되는 것을 이용하여, 마지막에 step에 bridge_length를 더해주었다. 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step