프로그래머스 '다리를 지나는 트럭' 파이썬 풀이

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

프로그래머스

def solution(length, threshold, trucks):
    answer = 0
    bridge = [0]*length # 다리를 우선 길이만큼 0으로 세팅
    cur_weight = 0
    trucks = trucks[::-1] 
    # trcuks.pop(0) 대신 trucks.pop()을 사용하기 위해 리스트를 뒤집어줌
    
    while trucks: # 트럭이 남아있을때까지만 반복문
        answer += 1 # 반복문이 한번 돌때마다 1초씩 증가
        cur_weight -= bridge.pop(0)
        # 다리 위에서 트럭 한대가 빠져 나갔으니까 무게를 빼줌
        
        w = trucks.pop() if cur_weight + trucks[-1] <= threshold else 0
        # 만약 현재무게에서 트럭이 한대 더 들어와도 다리가 버틸수 있는 무게보다
        # 적다면 trucks에서 트럭을 다리에 추가시키고 아니라면 0으로 세팅한다.
        
        cur_weight += w
        # 다리 무게에 w를 추가한다.
        
        bridge.append(w)
        # 그리고 다리에 w를 추가시킨다.
        
    return answer + len(bridge) 
    # 트럭이 다 다리에 올라갔으면 다리 길이만큼 초를 증가시키면 된다.
    
"""
cur_weight로 sum()을 대체하였다.
sum은 리스트길이(O(n))만큼의 시간이 걸리기 때문에 변수 하나를 두어 O(1)로 해결하였다.

trucks를 pop(0)을 하지 않고, pop()을 하기위해 
리스트를 뒤집어준 이유도 시간복잡도를 줄이기 위해서이다.

trucks.pop(0)은 O(n)의 시간복잡도를 가지고 pop()은 O(1)이다.
그렇기 때문에 처음 한번만 리스트를 뒤집어 준다면 효율이 좋아질 것이라고 판단했다.
"""