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

1. 문제 - 프로그래머스 다리를 지나는 트럭

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

 

해당 문제는 큐를 활용하여 푸는 문제다.

예시에서 대기 트럭 - 다리를 건너는 트럭 - 다리를 지난 트럭으로 움직이는 상황을 보면 먼저 들어간 데이터가 먼저 빠져나오는 (선입선출) 형태에서 큐 자료구조를 활용하는 문제임을 짐작할 수 있다.

 

✅ 풀이

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque([0] * bridge_length)  # 다리 위 상태 (처음엔 트럭 없음 → 0으로 채움)
    answer = 0  # 경과 시간
    bridge_weight = 0  # 현재 다리 위 총 무게
    truck_weights = deque(truck_weights)  # 대기 중인 트럭 리스트
    
    while bridge:
        answer += 1  # 1초 경과
        bridge_weight -= bridge.popleft()  # 다리를 지난 트럭(혹은 0)이 나감
        
        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                # 다음 트럭이 올라갈 수 있다면, 다리에 트럭 추가
                truck = truck_weights.popleft()
                bridge.append(truck)
                bridge_weight += truck
            else:
                # 다리 무게 초과되면, 트럭 대신 0을 넣어 한 칸 시간 보내기
                bridge.append(0)
    
    return answer

 

처음에는 이 풀이가 잘 이해가 안됐는데, 시뮬레이션 해보면 왜 이런 풀이가 나오는지 이해할 수 있다.

 

[시뮬레이션]

answer(초)	bridge(다리 상태)	bridge_weight(다리 위 무게)	truck_weights(대기 중인 트럭)
0	[0, 0]	0	[7, 4, 5, 6]	[]
1	[0, 7]	7	[4, 5, 6]	[] ← 7 올라감
2	[7, 0]	7	[4, 5, 6]	[] ← 1칸 이동
3	[0, 4]	4	[5, 6]	[7] ← 4 올라감
4	[4, 5]	9	[6]	[7]
5	[5, 0]	5	[6]	[7, 4]
6	[0, 6]	6	[]	[7, 4, 5]
7	[6, 0]	6	[]	[7, 4, 5]
8	[0, 0]	0	[]	[7, 4, 5, 6] → 종료!

 

1) bridge에는 최대 bridge_length 길이만큼 트럭이 올라갈 수 있고, 0초에는 아무 트럭도 올라가있지 않으므로 [0, 0]이고 다리 위 트럭들의 무게는 0이다. (bridge_weight = 0)

- deque을 사용한 이유는 다리에서 먼저 진입한 차를 뺄때 (pop(0)) deque의 popleft가 더 빠르기 때문에 사용한다.

    bridge = deque([0] * bridge_length)  # 다리 위 상태 (처음엔 트럭 없음 → 0으로 채움)
    answer = 0  # 경과 시간
    bridge_weight = 0  # 현재 다리 위 총 무게
    truck_weights = deque(truck_weights)  # 대기 중인 트럭 리스트

 

2) 다리에 트럭이 남아있을때까지는 (while bridge), 1초가 지날때마다 다리를 건너고 있는 트럭이 다리를 빠져나간다고 가정한다.

    while bridge:
        answer += 1  # 1초 경과
        bridge_weight -= bridge.popleft()  # 다리를 지난 트럭(혹은 0)이 나감

 

3) 그리고 현재 다리위의 무게(bridge_weight)에 대기중인 트럭을 더했을 때 기준선인 weight 이내라면 해당 트럭을 다리 위에 올린다.

        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                # 다음 트럭이 올라갈 수 있다면, 다리에 트럭 추가
                truck = truck_weights.popleft()
                bridge.append(truck)
                bridge_weight += truck
            else:
                # 다리 무게 초과되면, 트럭 대신 0을 넣어 한 칸 시간 보내기
                bridge.append(0)

 

아닌 경우에는 0을 추가하게 되는데, 이부분은 첫번째 예시의 다음과 같은 부분을 보면 왜 이렇게 했는지 이해할 수 있다.

1 ~ 2초 사이에 현재 다리위에 있는 7과 대기중인 트럭들 중 맨 앞 트럭인 4를 더하게 되면 11, 즉 첫번째 예시의 weight인 10을 초과하게 된다.

이 경우에는 다리 위에 트럭이 올라갈 수 없으므로 1초 더 시간을 보내야한다.

따라서 트럭을 올리지 않고 시간을 끌기위해 다리 위의 무게에 영향을 주지 않는 0을 추가한다. (4가 올라가기 전까지 2초가 소요됨을 알 수 있음)

 

따라서 위 [시뮬레이션]이랑 연관지어서 보면

0	[0, 0]	0	[7, 4, 5, 6]	[]
1	[0, 7]	7	[4, 5, 6]	[] ← 7 올라감
2	[7, 0]	7	[4, 5, 6]	[] ← 1칸 이동

 

0을 추가함으로써 트럭을 올리지 않은 상태로 시간을 끈다고 할 수 있겠다.

 

이 방법을 떠올리는것도, 이해하기도 굉장히 어려웠던 문제였다.

나중에 한번 더 다시 풀어볼것..!