[프로그래머스 알고리즘 Kit] 스택/큐 - 다리를 지나는 트럭

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

프로그래머스

 

 

 

문제설명

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

 

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어진다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성해야한다. 예시는 위 링크를 참고하자.

 

 

제한사항

bridge_length는 1 이상 10,000 이하이다.
truck_weights의 길이는 1 이상 10,000 이하이다.

 

 

구현

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge = deque([0]*bridge_length, maxlen=bridge_length)
    deq = deque(truck_weights)
    bridge_sum = sum(bridge) #sum은 O(n)으로 반복문안에 사용하면 시간복잡도가 증가한다..
    while bridge:
        time += 1
        item = bridge.popleft()
        print(bridge)
        bridge_sum -= item
        if deq:
            if bridge_sum + deq[0] > weight:
                bridge.append(0)
                print(bridge)
            else:
                item = deq.popleft()
                bridge_sum += item
                bridge.append(item)
                print(bridge)


    return time

 

 

- 트럭의 순서가 고정되어있고 truck_weights의 순서대로 bridge를 건너야하므로 선입선출 queue를 활용해야한다.

- 첫 구현에서 시간초과가 떠서 여러 블로그들을 참고하다보니 실패한 원인을 알게되었다. 

- sum함수가 O(n)이기에 매 반복문마다 사용할 경우 시간이 기하급수적으로 늘어난다는 점에서 시간초과가 뜰 경우 sum함수를 사용하면 안된다는 점을 배웠다.