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

문제 보기

이 문제는 스택/큐 문제이다.

쉬운 문제인 줄 알았는데, 자꾸 한 가지 생각에 꽂히다 보니 문제를 푸는데 시간이 걸렸다.

 

문제를 푼 로직은 다음과 같다.

1. 다리 위를 지나고 있는 트럭에 대해, 다리 위에서 소요한 시간을 센다. (나의 경우 다리 길이에서부터 1씩 감소시켰다.) (12~14번째 줄)
2. 만약 다리 위를 지나고 있는 트럭 중 가장 첫 번째 트럭이 다리의 길이만큼 시간을 소모했으면, 다리를 통과시킨다. (16~19번째줄)
3. 만약 대기하고 있는 트럭이 있고, 다리를 지나갈 공간이 있으면 트럭을 출발시킨다. (21~27번째 줄)
4. 소요된 시간을 센다. (28번째 줄)

 

다리 위를 지나고 있는 트럭부터 계산을 하고 대기하고 있는 트럭을 신경써야 했지만, 나는 대기하고 있는 트럭부터 신경을 써서 출발시키려다보니 문제가 더 복잡해졌다.

간단한 문제인데 쓸 데 없이 한 가지 생각에 붙잡혀 있다보니 아까운 시간만 날렸다.. 

 

from collections import deque
 
 
def solution(bridge_length, weight_limit, truck_weights):
    answer = 0
    waiting = deque(truck_weights)
    passing = deque()
    
    bridge_weight = 0
    while waiting or passing:
        
        # count time for the trucks on the bridge
        for i in range(len(passing)):
            passing[i][1] -= 1
        
        # if the first truck on the bridge is about to pass
        if passing and passing[0][1] == 0:
            weight, _ = passing.popleft()
            bridge_weight -= weight
        
        # if there's any waiting truck
        if waiting:
            # if the bridge is available
            if len(passing) < bridge_length and bridge_weight + waiting[0] <= weight_limit:
                weight = waiting.popleft()
                passing.append([weight, bridge_length])
                bridge_weight += weight
        answer += 1
        
    return answer