[스택/큐] 프로그래머스 Lv2. 다리를 건너는 트럭 - Python

🗂️ 문제

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583#

프로그래머스

 

 

💡 접근법

트럭을 큐(다리)에 차례로 진입시키는데, 이때 시간(second)을 기준으로 한다.

시간을 기준으로 총 두 가지의 작업을 수행하며, total_weight 변수를 통해 큐(다리)의 전체 무게를 체크한다.

1. 큐에서 0번째 트럭이 다리를 건넜는지 확인한다.만약 다리를 건넜다면, 큐에서 해당 트럭을 삭제한다. (total_weight에서 해당 트럭의 무게도 뺀다)
   • 경과 시간 = 현재 시간 - 진입 시간을 확인하여 트럭이 다리를 모두 건넜는지 여부를 확인한다.
2. 새로운 트럭이 다리에 진입할 수 있는지 확인한다.
   • 현재 다리의 모든 트럭 무게(total_weight)에 새로운 트럭의 무게를 더했을 때 다리의 총량을 체크한다.
   • 만약, 새로운 트럭이 진입해도 다리의 총량보다 전체 무게가 적다면, 새로운 트럭을 다리에 진입시킨다. 이때 경과 시간 계산을 위해 트럭을 진입시킬 때 (트럭의 무게, 진입 시간)을 큐에 삽입한다. (total_weight에 새로운 트럭의 무게를 더한다)

최종적으로 모두 건넌 시간은 second+1한 값이다.

 

😎 내 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    seconds = 0
    
    truck_weights = deque(truck_weights)
    total_weight = truck_weights[0]
    queue = deque([(truck_weights.popleft(), seconds)])
    while queue:
        seconds += 1
        
        if seconds - queue[0][1] == bridge_length:  # 트럭이 다리를 모두 건넜는지 확인
            total_weight -= queue[0][0]
            queue.popleft()
        
        if truck_weights and total_weight + truck_weights[0] <= weight:  # 새로운 트럭 진입 가능 여부 확인
            total_weight += truck_weights[0]
            queue.append((truck_weights.popleft(), seconds))
   
    return seconds+1