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

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

 

💭 문제 이해

 

트럭이 순서대로 대기하고 있고,

다리가 견딜 수 있는 무게 내에서 최대한 빠르게 모든 트럭이 통과하는 시간을 구하는 문제이다.

 

트럭들이 대기하다가 순서대로 지나가고, 다리 또한 한 방향으로 지나가기 때문에 Queue가 떠올랐다.

 

트럭이 지나가는 다리를 bridge라는 이름으로 queue(deque 사용)를 선언하고

대기 중인 트럭들을 waiting이라는 이름으로 queue를 선언했다.

 

대략적인 코드 구조는 다음과 같다.

 

0. 0초부터 1초 씩 증가하며 시간을 기록한다.

1. bridge가 비어있지 않다면 지금 시점에 지나가야하는 트럭은 dequeue 시킨다. (다리를 빠져나간다.)

2. bridge와 waiting에 남은 트럭이 없다면 현재 시간을 리턴함으로 반복문을 종료시킨다. (모든 차량을 처리한 경우)

3. 대기중인 차량이 존재한다면 다리의 총 무게를 체크해보고 현재 시점 기록과 함께 bridge에 진입시킨다.

    (tuple(무게, 시간)을 bridge에 enqueue 시키는 것)

 

 

 

 

구현 언어: Python

 

from collections import deque


def solution(bridge_length, weight, truck_weights):
    time = 0
    weight_sum = 0
    bridge, waiting = deque(), deque(truck_weights)
    
    while True:
        time += 1
        # 체크하면서 이번 타임에 나가야할 트럭을 내보낸다.
        if bridge:  # 다리가 비어있지 않은 상태일 때
            if time == bridge[0][1] + bridge_length:
                weight_sum -= bridge[0][0]
                bridge.popleft()
        # 모든 차를 처리했다면 종료
        if (not bridge) and (not waiting):
            return time
        # 다리가 견딜 수 있는 무게에 한하여 추가할 차량을 추가한다.
        if waiting:
            if weight_sum + waiting[0] <= weight:
                bridge.append((waiting[0], time))  # 현재 시점 기록과 함께 다리에 진입
                weight_sum += waiting[0]  # 다리의 총 무게 갱신
                waiting.popleft()  # 대기열에서 제거
    return time