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

문제 보기

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

---

문제 해결

대기 트럭 리스트에서 제일 앞의 원소를 제거하고 다리를 건너는 트럭의 리스트에서 원소를 추가하는 일을 반복하는 것을 보고 큐를 이용하여 문제를 해결하는 것으로 추측하였다. 

처음에 7 트럭이 다리를 건널 때 왜 2초가 걸리는지 이해가 가지 않았고 while 반복문 종료 조건을 어떻게 설정해야할지 감이 잡히지 않는 문제였다.

여러 사람들의 풀이를 보았지만 완벽히 이해가 되지 않았고 실제 테스트에서 이와 같은 문제가 나오면 솔직히 이러한 로직을 생각해서 풀지는 못할 것 같다.

 

아래는 소스코드 반복문 돌아가는 순서대로 큐의 상태를 나열한 것이다.

경과시간	다리 위 트럭의 무게	다리를 건너는 트럭	대기 트럭
time	bridge_weight	bridge	wait_truck
0	② 0 -> 0	① [0,0] → [0]	[7,4,5,6]
⑥ 1	④ 7	⑤ [0,7]	③ [4,5,6]
	⑧ 0	⑦ [7]	⑨ [4,5,6]
2	7	[7,0]	[4,5,6]
	0	[0]	[4,5,6]
3	4	[0.4]	[5,6]
	4	[4]	[5,6]
4	9	[4,5]	[6]
	5	[5]	[6]
5	5	[5,0]	[6]
	0	[0]	[6]
6	6	[0,6]	[]
7	6	[6]	[]
8	0	[]	[]

 

 

 

소스 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge_weight = 0 # 다리 위의 트럭 무게
    wait_truck = deque(truck_weights) # 대기 트럭 
    bridge = deque([0 for _ in range(bridge_length)]) # 다리 길이만큼 0으로 채우기
    
    while wait_truck or bridge_weight > 0: # 대기 트럭이 있거나 이동 중인 트럭이 있는 동안 반복하기
        tmp = bridge.popleft() # 다리에서 하나 제거
        bridge_weight -= tmp
        
        if wait_truck and bridge_weight + wait_truck[0] <= weight: # 새 트럭이 다리에 올라갈 수 있을 경우
            now = wait_truck.popleft()
            bridge_weight += now      
            bridge.append(now) # 대기 트럭에서 하나 빼서 다리에 올림
            
        else: # 새 트럭이 다리에 올라갈 수 없을 경우
            bridge.append(0) # 큐의 오른쪽에 0을 삽입하여 다리 길이를 유지    
        time += 1
        
    return time