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

코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    cnt = 0
    brg = [0]*bridge_length
    brg = deque(brg)
    truck_weights = deque(truck_weights)
    brg_sum = 0
    while brg:
        cnt += 1
        tmp = brg.popleft()
        brg_sum -= tmp
        if truck_weights:
            if brg_sum + truck_weights[0] <= weight:
                t = truck_weights.popleft()
                brg_sum += t
                brg.append(t)
            else:
                brg.append(0)
    return cnt

풀이

• 처음에 문제 이해를 잘 못했는데, 출처를 보니 다리의 길이가 10이면 한 트럭이 다리를 건너는데 10초가 걸린다고한다.
• 0으로 다리 길이만큼의 배열을 만들어서 반복할때 다리에 올라갈 수 있나 없나를 체크한다.
• 주의할 점은 다음 트럭이 다리에 올라갈 수 있냐 없냐를 if문으로 확인할 때, sum함수로 현재까지 다리에 있는 트럭의 무게를 계산할경우 시간복잡도가 O(n)이므로 시간 초과가 발생한다.
• 다리의 무게를 0으로 초기화해서, 다리에 올라갈때 더해주고, 내려올때 빼주는 것으로 해결해야 시간초과 없이 풀 수 있다.