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

📌 문제

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

📌 풀이

풀이 1 - (5번 테스트케이스 실패)

1. truck_weights 왼쪽에서 빼기 때문에 deque 자료구조로 바꾸어 준다.
2. bridge_length만큼 원소가 들어갈수 있도록 새로운 deque 자료구조를 생성한다. (이는 현재 bridge위에 있는 차와 무게를 나타낸다.)
3. truck_weights에서 대기하는 자동차가 없을때까지 반복문을 반복한다.
   3-1. truck_weights에서 가장 앞에 있는 자동차의 무게와 bridge의 무게를 합하여 weight(다리 제한무게)를 넘지 않는다면 truck_weights의 첫번째 자동차를 빼서 bridge에 넣어준다. 그리고 초를 세기위해 answer +1을 해준다.
   3-2. truck_weights에서 가장 앞에 있는 자동차의 무게와 bridge의 무게를 합하여 weight(다리 제한무게)를 넘는다면 bridge에 0을 넣어준다. 그리고 초를 세기위해 answer +1을 해준다.

(주의!) bridge위의 자동차무게를 구할때 sum(bridge)가 아닌 sum(bridge) - bridge[0]으로 해야한다.

0초: [0,0]
1초: [0,7]
2초: [7,0]
3초: [0,0][0,4]
위의 예시와 같이 "7"이 나가는 동시에 "4"가 들어오는데 이것은 1초 내에 함께 이루어진다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0 for _ in range(bridge_length)],maxlen=bridge_length)
    
    while len(truck_weights):
        estimated = truck_weights[0] + sum(bridge) - bridge[0]
        if estimated <= weight:
            temp = truck_weights.popleft()
            bridge.append(temp)
            answer += 1
        else:
            bridge.append(0)
            answer += 1
            
    return answer + bridge_length

풀이 2 - (성공)

이전 코드에서 시간 초과가 발생하는 이유는 estimated = truck_weights[0] + sum(bridge) - bridge[0] 부분이다. 이 부분은 매 반복마다 다리 위의 트럭들의 무게를 모두 더하는 작업을 수행하고 있습니다. 이 작업은 sum(bridge)를 통해 다리 위의 트럭 무게를 더하는 것인데, 이러한 작업은 시간복잡도가 O(다리의 길이)가 되며, 다리 위에 있는 트럭의 수가 다리의 길이에 가까워질수록 계산 시간이 길어지게 된다.

따라서 테스트 케이스 시간초과 문제를 해결할 수 있는 핵심은, "다리 위의 트럭들의 무게 합을 매번 다시 계산하지 않고도 관리할 수 있는 방법"을 찾는 것이다.

'current_weight' 변수를 통해 현재 다리 위의 트럭 무게의 합을 유지하면서, sum(bridge) 계산을 피하고자 한다. 이렇게 함으로써 불필요한 계산을 줄이고 시간복잡도를 개선할 수 있다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0] * bridge_length, maxlen=bridge_length)
    current_weight = 0
    
    while len(truck_weights):
        if len(bridge) == bridge_length:
            current_weight -= bridge.popleft()
        
        if current_weight + truck_weights[0] <= weight:
            current_truck = truck_weights.popleft()
            bridge.append(current_truck)
            current_weight += current_truck
        else:
            bridge.append(0)
            
        answer += 1
        
    return answer + bridge_length

reference

• stack 정리글