[Programmers] 다리를 지나는 트럭

문제

요약

길이가 length인 다리가 최대 weight 무게를 견딜 수 있을 때,

truck_weights의 트럭들이 모두 다리를 건너려면 얼마나 걸리는가

 

---

풀이

풀이1(오답)

첫번째 풀이의 접근 자체는 나쁘지 않았던 것 같다.

현재 다리 위의 트럭들의 무게와 새로 들어오는 트럭의 합이 기준보다 초과일때,

제일 앞에 있는 트럭이 다리를 다 지날 때까지는 진입을 못한다.

 

마지막 트럭이 다리 위에 올라오고 나서는 다리 길이만큼 시간이 더 걸리기 때문에 마지막에 다리길이를 한번더 더해준다.

 

이 풀이는 다리 중간 쯤까지 차가 이동해 있었을 경우를 파악하지 못한다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    head = 0
    q = deque([])
    
    for truck in truck_weights:
        if sum(q) + truck > weight:
            answer += bridge_length
            q.popleft()
        else:
            answer += 1
        q.append(truck)  

        while len(q) > bridge_length:
            q.popleft()
            answer += 1

    return answer+bridge_length

 

 

풀이2(정답)

무게를 초과할 때 무게 대신 0을 추가하는 것까지는 파악했는데 그 뒤로 계속 풀리지 않았다.

그리고 나서는 total로 무게를 그때그때 구하는 것 대신 sum(bridge)를 사용했다가 시간초과가 발생했다.

deque여부와 상관 없이 sum은 리스트 길이 n만큼 O(n)의 시간이 걸리기 때문에 시간 초과가 된다.

오늘도 하나 알아가는 하루 :)

from collections import deque
def solution(length, weight, truck_weights):
    answer = 0
    trucks = deque(truck_weights)
    bridge = deque([0] * length)
    total = 0
    
    while len(trucks):
        t = bridge.popleft()
        answer += 1
        total -= t
        
        if total + trucks[0] > weight:
            bridge.append(0)
        else:
            t = trucks.popleft()
            bridge.append(t)
            total += t
        
    return answer+length