[Programmers] 다리를 지나는 트럭 (Python3)

문제

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

문제 풀이

처음에는 아예 실제 다리랑 똑같이 움직이는 큐를 만드려고 아예 0을 biridge_length만큼 데크로 만든 뒤 새로 들어오면 0이 popleft()되고 다음 차의 무게가 들어와 하나씩 밀리는 식으로 해서 그때마다 시간을 1초씩 추가해서 만들려고 했다. 사실 내심 시간초과가 뜰거라고 생각했는데, 진짜 시간 초과가 떠서 더 간단한 코드를 생각하게 되었다.

처음에는 모든 경우의 수를 다 제각각 코딩했었는데, 다시 간단하게 생각해보니 그냥 계속 time을 1씩 더하면서 큐를 밀어내주면 훨씬 간단하게 시간을 측정할 수가 있었다.

근데 이렇게 풀어도 자꾸 테스트 케이스 하나에서 시간초과가 떴다!
진짜 아무리봐도 더 줄일 수가 없다고 생각했는데 문제는 sum()이었다.

다리위의 차량들의 무게의 총합을 구하려고 sum(queue)를 사용하고 있었는데, 이게 시간복잡도를 꽤 잡아 먹고 있었다.

sum()을 사용하지말고 따로 다리위의 차량들의 무게를 따로 저장하는 변수를 만들어 차가 올라갈때나 내려올때 변수가 달라지게 만들었다. 앞으로 시간초과가 이유없이 뜬다면 sum() 함수를 없애줌으로써 시간을 절약할 수 있다는걸 알게 되었다.

코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    queue = deque([0]* bridge_length)
    bridge_weight = 0
    while queue:
        time+=1
        out_truck = queue.popleft()
        
        if out_truck != 0:
            bridge_weight-=out_truck
            
        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                in_truck = truck_weights.pop(0)
                queue.append(in_truck)
                bridge_weight+=in_truck
                
            else:
                queue.append(0)
    return time

solution(2, 10, [7, 4, 5, 6])

8

잘못 풀었던 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    
    queue = deque(0 for _ in range(bridge_length))
    time = 0
    
    for i in range(len(truck_weights)):
        
        if sum(queue)+ truck_weights[i] <= weight and 0 < queue.count(0):
            queue.popleft()
            queue.append(truck_weights[i])
            time+=1
        else:
            while 1:
                queue.popleft()
                queue.append(0)
                time+=1
                if queue.count(0) == bridge_length or sum(queue)+ truck_weights[i]<= weight:
                    queue.popleft()
                    queue.append(truck_weights[i])
                    break
    
    while queue:
        queue.popleft()
        time+=1
    return time