알고리즘 코드카타 102 - 다리를 지나는 트럭

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

프로그래머스

 

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 이하입니다.

 

예시

bridge_length	weight	truck_weights	return
2	10	[7, 4, 5, 6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

 

트럭들이 다리를 지나가는데 걸리는 시간을 계산하는 알고리즘, 다리의 길이, 다리의 무게제한, 트럭의 순번(+무게)가 인풋으로 주어진다.

문제에는 트럭 한대가 다리를 통과하는데 시간이 얼마나 걸리는지 적혀있지 않았다. 하지만 예시를 보니 다리의 길이 1만큼 가는데 1초가 소요된다는 것을 알 수 있었다. 즉 다리의 길이는 한번에 이동할 수 있는 트럭의 숫자와 동시에 트럭이 통과하는 시간을 의미한다.

 

가장 먼저 다리의 길이를 리스트로 생성한다.

def solution(bridge_length, weight, truck_weights):
    second = 0
    bridge = [0] * bridge_length
    
    return bridge

 

0으로 이루어진 리스트인 bridge를 생성했다. 그리고 sum(bridge)를 사용하면 현재 다리위에 있는 트럭들의 무게를 알 수 있다.

 

다음으로는 트럭을 다리에 진입시킨다. bridge.pop(0)로 bridge[0]을 제거하고 bridge.append(truck_weights[0])로 트럭을 진입시킨 후 truck_weights.pop(0)로 진입한 트럭을 제거해주면 된다. 그리고 트럭이 진입했으니 1초를 더해준다.

def solution(bridge_length, weight, truck_weights):
    second = 0
    bridge = [0] * bridge_length
    bridge.pop(0)
    bridge.append(truck_weights[0])
    truck_weights.pop(0)
    print(bridge, truck_weights)
        
    return second

테스트 1
입력값 〉	2, 10, [7, 4, 5, 6]
출력 〉	[0, 7] [4, 5, 6]

 

첫번째 트럭이 다리에 진입했다. 이제 truck_weights가 빌때까지(= 모든트럭이 진입할 때까지) 해당 과정을 반복하면 된다.

def solution(bridge_length, weight, truck_weights):
    second = 0
    bridge = [0] * bridge_length
    while truck_weights:
        second += 1
        bridge.pop(0)
        bridge.append(truck_weights[0])
        truck_weights.pop(0)
        print(bridge, truck_weights, second)
        
    return second

테스트 1
입력값 〉	2, 10, [7, 4, 5, 6]
출력 〉	[0, 7] [4, 5, 6] 1 [7, 4] [5, 6] 2 [4, 5] [6] 3 [5, 6] [] 4

 

트럭이 순서대로 다리에 진입하고 빠져나가는 과정과 걸리는 시간이 출력되었다. 다음은 다리위의 트럭의 무게가 제한무게가 넘지 않도록 해야한다. 현재무게(sum(bridge)) + 진입예정인 트럭의 무게(truck_weights[0])가 무게제한(weight)보다 클 경우 트럭을 진입시키지 않아야한다.

while truck_weights:
        second += 1
        bridge.pop(0)
        if sum(bridge) + truck_weights[0] <= weight:
            bridge.append(truck_weights[0])
            truck_weights.pop(0)
        else:
            bridge.append(0)
        print(bridge, truck_weights, second)

테스트 1
입력값 〉	2, 10, [7, 4, 5, 6]
출력 〉	[0, 7] [4, 5, 6] 1 [7, 0] [4, 5, 6] 2 [0, 4] [5, 6] 3 [4, 5] [6] 4 [5, 0] [6] 5 [0, 6] [] 6

 

다음 트럭이 진입할때, 무제제한이 초과될 경우 트럭을 진입시키지 않도록 했다. 이제 마지막으로 출력된 second에는 마지막 트럭이 진입한 시간이 기록되게 된다. 따라서 return은 second + bridge_length이다.

 

def solution(bridge_length, weight, truck_weights):
    second = 0
    bridge = [0] * bridge_length
    
    while truck_weights:
        second += 1
        bridge.pop(0)
        if sum(bridge) + truck_weights[0] <= weight:
            bridge.append(truck_weights[0])
            truck_weights.pop(0)
        else:
            bridge.append(0)
        
    return second + bridge_length

시간초과...

 

실행결과 풀이 방법 자체는 정답이었다. 하지만 코드의 계산 속도가 상당히 오래걸리고 말았다...

아마도 sum()의 시간복잡도가 문제일 것이다. 트럭의 무게제한을 계산할 때, sum()을 사용하는 대신 현재 다리 위에 있는 트럭의 무게를 계산하는 변수를 추가해서 코드를 개선해보자.

 

def solution(bridge_length, weight, truck_weights):
    second = 0
    bridge = [0] * bridge_length
    current_weight = 0
    
    while truck_weights:
        second += 1
        current_weight -= bridge[0]
        bridge.pop(0)
        
        if current_weight + truck_weights[0] <= weight:
            current_weight += truck_weights[0]
            bridge.append(truck_weights[0])
            truck_weights.pop(0)
        else:
            bridge.append(0)
        
    return second + bridge_length

 

sum(bridge)를 사용하는 대신에 current_weight변수를 생성해서 현재 다리 위에 있는 트럭들의 무게를 따로 저장했다. 트럭이 다리에 진입할 때(= bridge.append(truck_weights[0])) 트럭의 무게에 더해지고(current_weight += truck_weights[0]) 다리의 가장 앞의 원소가 제거될 때(bridge.pop(0)) 가장 앞에 있는 무게만큼 빼주었다.(current_weight -= bridge[0])

통과!

 

결과는 통과이다. 위의 코드에서 시간문제로 통과하지 못했던 테스트 5는 물론이고 코드 자체가 개선된 덕분에 전체적인 실행 시간이 감소했다. sum()의 시간 복잡도가 O(n)이라는 것은 이번에 처음 알게 되었다... 반복문 사이에 sum()을 사용하는 것은 자제해야할 것같다.