[Programmers] Lv2. 다리를 지나는 트럭 Python 문제 풀이

문제

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

프로그래머스

 

어떻게 풀었는가

다리를 고정 길이의 큐로 모델링하는 것이 핵심이다.

아이디어

다리 위의 상태를 bridge_length 크기의 deque로 표현하고, 초기값을 모두 0으로 채운다. 매 초마다 deque의 앞에서 하나를 빼고(다리를 빠져나감), 뒤에 새 트럭을 넣거나 0을 넣는(빈 칸이 전진) 방식으로 시뮬레이션한다.

구현 흐름

1. 매 초마다 bridge의 맨 앞 값을 popleft하고, 그 무게만큼 현재 다리 위 총 무게(cur_weight)에서 뺀다.
2. 대기 중인 다음 트럭의 무게를 더했을 때 weight 이하라면 트럭을 다리에 올린다. 아니라면 0을 넣어 빈 칸을 유지한다.
3. 대기 트럭이 모두 소진되고 다리 위 무게가 0이 되면 종료한다.

다리 자체를 큐로 표현하면 "몇 초 후에 빠져나가는가"를 별도로 계산할 필요 없이, deque 길이가 곧 다리 통과 시간을 보장해준다.

시간복잡도

트럭 수를 T, 다리 길이를 L이라 하면 최악의 경우 매 초 트럭이 올라가지 못하고 0만 채워지는 상황이 반복되므로 O(T × L)이다. deque 연산은 모두 O(1)이므로 제한 조건(각각 최대 10,000) 내에서 충분하다.

코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge = deque([0] * bridge_length)
    cur_weight = 0
    trucks = deque(truck_weights)

    while trucks or cur_weight > 0:
        time += 1
        cur_weight -= bridge.popleft()

        if trucks and cur_weight + trucks[0] <= weight:
            t = trucks.popleft()
            bridge.append(t)
            cur_weight += t
        else:
            bridge.append(0)

    return time