====== 다리를 지나는 트럭 ======

===== 풀이 =====
  * 다리 위에 있는 트럭들을 큐로 관리해주면 쉽게 처리되는 문제이다.
  * 그것을 나이브하게 풀면, 매 초마다 새 트럭이 다리에 올라갈수 없는 경우에 무게 0짜리의 가상 트럭을 대신 다리에 올리는 것처럼 구현할 수 있고, 이 경우에는 전체 걸린 시간, 즉 O(n*m)에 풀린다 (n=트럭의 갯수, m=다리의 길이). 비효율적이지만, 정답에 올라가있는 대부분의 코드가 이러한 방식으로 구현되어있다. (코드 1)
  * 트럭마다 트럭의 무게와 다리에 올라간 시간을 함께 묶어서 큐에 저장하면, 가상 트럭 없이 실제 트럭들에 대해서만 큐에 한번씩만 추가/삭제하는 것으로 전체 걸린 시간을 계산할 수 있다. 이렇게 하면 O(n)에 해결 가능하다. (코드2)


===== 코드 =====
==== 코드 1 - O(n*m) ====
<dkpr py>
"""Solution code for "Programmers 42583. 다리를 지나는 트럭".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42583
- Solution link: http://www.teferi.net/ps/problems/programmers/42583
"""

import collections 


def solution(bridge_length, weight, truck_weights):
    weight_sum = 0
    trucks_on_bridge = collections.deque([0] * bridge_length)
    sec = 0
    for truck_weight in truck_weights:
        while True:
            sec += 1
            weight_sum -= trucks_on_bridge.popleft()
            if weight_sum + truck_weight <= weight:
                trucks_on_bridge.append(truck_weight)
                weight_sum += truck_weight
                break
            trucks_on_bridge.append(0)
    return sec + bridge_length
</dkpr>


==== 코드 2 - O(n) ====
<dkpr py>
"""Solution code for "Programmers 42583. 다리를 지나는 트럭".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42583
- Solution link: http://www.teferi.net/ps/problems/programmers/42583
"""

import collections

Truck = collections.namedtuple('Truck', ['weight', 'enter_time'])


def solution(bridge_length, weight, truck_weights):
    weight_sum = 0
    trucks_on_bridge = collections.deque()
    cur_sec = 0
    for cur_truck_weight in truck_weights:
        cur_sec += 1
        if (trucks_on_bridge and
                trucks_on_bridge[0].enter_time + bridge_length <= cur_sec):
            weight_sum -= trucks_on_bridge.popleft().weight
        while weight_sum + cur_truck_weight > weight:
            out_truck = trucks_on_bridge.popleft()
            cur_sec = out_truck.enter_time + bridge_length
            weight_sum -= out_truck.weight
        trucks_on_bridge.append(Truck(cur_truck_weight, cur_sec))
        weight_sum += cur_truck_weight
    return cur_sec + bridge_length
</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_2}}