★★★ 스택/큐 - 다리를 지나는 트럭 (프로그래머스)

<문제>

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

프로그래머스

 

 

<코드>

from collections import deque

def solution(bridge_length, weight, truck_weights):
    l = len(truck_weights)
    bridge = deque([0] * bridge_length)
    truck_list = deque(truck_weights)
    S, time = 0, 0
    
    while len(truck_list) !=0:
        b = bridge.popleft()
        S -= b
        if S + truck_list[0] > weight: # sum 함수에서 시간 초과 발생
            time +=1
            bridge.append(0)
        else:
            t = truck_list.popleft()
            bridge.append(t)
            S += t
            time +=1
            if len(truck_list) == 0:
                time += bridge_length
                break
    return time
    
    # while len(truck_list) !=0:
    #     bridge.popleft()
    #     if sum(bridge) + truck_list[0] > weight: # sum 함수에서 시간 초과 발생
    #         time +=1
    #         bridge.append(0)
    #     else:
    #         bridge.append(truck_list.popleft())
    #         time +=1
    #         if len(truck_list) == 0:
    #             time += bridge_length
    #             break
    # return time

 

<풀이>

• 아래 코드는 단순히 무게에만 조건을 준 코드로 시간은 고려하지 않음
  • Ex) 다리가 견디는 최대 무게가 100일 때, 트럭 무게가 50 30 10 10 20인 순으로 갈 때, 50인 트럭이 빠지고는 20이 출발할 수 있음을 고려해야함

def solution(bridge_length, weight, truck_weights):
    on_bri_we = 0
    on_bri_tru = []
    time = 1
    for i in range(len(truck_weights)):
        w = truck_weights[i]
        on_bri_we = sum(on_bri_tru)
        if on_bri_we + w <= weight:
            if len(on_bri_tru) != 0 :
                time +=1
            on_bri_tru.append(w)
            if i == len(truck_weights)-1 :
                time +=bridge_length
        else:
            on_bri_tru = [w]
            time += bridge_length
            if i == len(truck_weights)-1 :
                time +=bridge_length
    return time

• sum을 반복문에 사용하면 시간복잡도가 올라가서 시간초과 문제가 발생할 수 있어 sum을 반복사용하는 것이 아닌 값 자체를 바로 이용하여 sum의 시간복잡도 O(N)의 반복 막기