[프로그래머스] 다리를 지나는 트럭 (Python)

💁🏻 나의 풀이

from collections import deque

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

    bridge.popleft()
    head = queue.popleft()
    bridge.append(head)
    answer = 1
    count = 1
    total = head

    while total > 0 or queue:
        head = bridge.popleft()
        if head > 0:
            total -= head
            count -= 1

        if queue and queue[0] + total <= weight and count < bridge_length:
            head = queue.popleft()
            bridge.append(head)
            total += head
            count += 1
        else:
            bridge.append(0)

        answer += 1

    return answer

• 우선 문제가 조금 불친절하다 (다리에 올라간 후부터 1시간에 1칸씩 이동한다는 전제조건이 명시되어있지 않음)
• 위 조건을 깨달은 다음부터는 다리의 입구에서 들어가고, 출구에서 빠져나오는 양상 파악 → queue 사용
• 다리를 하나의 queue로 상정하고 시간 당 한번씩 조건에 맞게 출구에서 pop, 입구에서 append 처리를 하면됨
• 위의 과정을 queue가 비어있지 않거나, 다리위에 트럭이 존재하는한 계속하면 됨
• weight 조건을 체크하기위해 매번 sum 함수를 사용하면 시간 복잡도가 늘어나서 안됨 → total이라는 변수로 매번 갱신해서 처리

📚 What I Learned

스택/큐 문제에서는 단순하게 생각

• append, pop 하는 각 단계를 한번에 여러개씩 처리하려 하기보다는
• 각 단계를 한번씩 여러번 반복해서 결과가 나오는 단순한 구조가 여러모로 좋은듯 (코드 구조, 구현 난이도 등등...)
• 생각보다 너무 시간이 오래 걸린 문제