[Programmers] 다리를 지나는 트럭

 

 

문제 

 

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

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

 

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

 

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

 

해설 코드 

def solution(bridge_length, weight, truck_weights):
# 트럭에 세울 수 있는 트럭의 개수만큼의 배열을 만들어준다. 
    trucks_on_bridge = [0] * bridge_length
    time = 0 
    # 트럭이 다리위에 존재할 때까지 반복문을 돌린다. 
    while len(trucks_on_bridge) != 0:
        time += 1
        trucks_on_bridge.pop(0)
        # 대기 중인 트럭이 존재하고 첫 번째로 대기중인 트럭과 현재까지 다리 위에 있는 트럭의 합이
        # weight 보다 작거나 같을 때 다리 위로 대기 중인 첫 번째 트럭을 보내고 대기 중인 트럭
        # 배열에서는 해당 트럭을 pop 한다. 
        if truck_weights:
            if sum(trucks_on_bridge) + truck_weights[0] <= weight:
                trucks_on_bridge.append(truck_weights.pop(0))
            else:
                trucks_on_bridge.append(0)
    return time

걸리는 시간 (time)	다리 위에 있는 트럭 (trucks_on_bridge)	대기 중인 트럭(truck_weight)
0	[0,0]	[7,4,5,6]
1	[0] -> [0,7]	[4,5,6]
2	[7] -> [7,0]
3	[0] -> [0,4]	[5,6]
4	[4] -> [4,5]	[6]
5	[5] -> [5,0]
6	[0] -> [0,6]	[]
7	[6]
8	[]

분석 > 이 해설 코드의 핵심 원리는 다리 위에 최대로 올라갈 수 있는 트럭의 개수만큼의 배열을 미리 만들어 두고, while 문을 돌면서 첫번째 원소를 pop 하는 동시에 대기 중인 첫 번째 트럭이 들어올 수 있는지 없는지를 weight를 기준으로 판단한 다음, 들어올 수 있으면 첫 번째로 대기 중인 트럭을 다리 위로 보내고 그렇지 않는 경우에는 0을 append 하여 대기 중인 트럭이 다음 차례를 기다리게 하는 원리이다. 결국 while 문 자체는 다리 위에 있는 트럭 배열의 길이가 빈배열이 될 때까지 반복해야 하며, 다리 위에 대기 중인 트럭을 보낼 때(다리 위에 있는 트럭 배열에 대기 중인 첫 번째 트럭을 append 할 때)는 반드시 대기 중인 트럭이 하나 이상 존재해야 한다. 처음 이 코드를 봤을 때는 이해가 잘 가지 않아서 직접 손으로 변화 과정을 따라 내려가 보니 코드의 전개 과정을 확실히 이해할 수 있었다. 

 

 

코딩테스트 연습 - 다리를 지나는 트럭