프로그래머스: 다리를 지나는 트럭

문제

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

 

문제 풀이

 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해준 순으로 건너려고 할 때, 다리에 올라갈 수 있는 무게 제한이 있다. 트럭은 1초에 다리 한 칸을 지나갈 때, 모든 트럭이 다리를 건너는데 걸리는 시간을 구하는 문제이다. 문제를 풀기 위해서는 다음과 같은 로직을 작성하면 된다.

 

• q에 초기 값을 0으로 다리 길이만큼 채운다.
• 다리에 올라갈 수 있는 트럭을 파악하기 위해, 현재 다리의 무게를 계산한다.
• 첫 트럭부터 다리 위에 올라갈 수 있는지 확인하고, 올라갈 수 있다면 해당 트럭의 무게를 큐에 추가한다.
  • 반대의 경우 트럭의 무게가 아닌, 0을 추가하여 시간을 계산할 수 있도록 한다.
• Queue가 빌 때까지 해당 작업을 반복하면, 무게에 따라 몇 초의 시간이 걸리는지 알 수 있다.

 

코드

from collections import deque


def solution(bridge_length, weight, truck_weights):
    answer, bridge_weight = 0, 0
    truck_weights = truck_weights[::-1]
    q = deque([0] * bridge_length)

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

 pop(0)를 하는 것이 pop()보다 오버헤드가 크기에, 트럭의 무게를 반전 시킨 후 pop()을 사용하여 트럭의 무게를 가져오도록 하였다.