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

문제

문제 링크

요약 1초에 거리 1씩 건널 수 있고 하중에 제한된 다리에 순서대로 들어오는 트럭이 모두 건너는데 걸리는 최단시간 구하기

접근 과정

1. 문제 난이도에 비해 생각을 많이 했던 것 같다. 트럭이 다리에 들어갈 때 마다 처리해도 좋을 것 같고, 모든 시간대에 대해 처리를 해도 은근히 가능해보였다. 그러다가 그 둘을 섞으면 그럭저럭 효율적인 방법이 될 것 같아 구현을 시작했다.

2. 트럭을 다리(큐) 위에 올릴 때마다 시간을 한 틱씩 증가시킨다. 이 때 다리 위에 있는 트럭들의 무게가 하중 제한을 넘긴다면 앞에 있는 것들을 빼가면서 시간을 점프시키는 방식이다. 별다른 전처리 없이도 O(N) 시간으로 처리할 수 있어 썩 괜찮은 알고리즘이라 생각한다 ㅋㅋ

소스 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0

    current_weight = 0
    bridge = deque()
    for tw in truck_weights:
        time += 1

        while current_weight + tw > weight:
            front = bridge.popleft()
            current_weight -= front[0]
            if front[1] + bridge_length > time:
                time = front[1] + bridge_length

        current_weight += tw
        bridge.append([tw, time])

    back = bridge.pop()    
    time = back[1] + bridge_length

    return time

이번에 파이썬의 deque 클래스를 처음 사용해봤는데 익숙치 않으니 조금 헤매는 부분이 있었다. popleft()가 있길래 당연히 popright()가 있겠지~ 했는데 그냥 pop()이더라 -_-;;