[프로그래머스/스택] 다리를 지나는 트럭 - 파이썬

하루정도 고민하고 힌트를 얻어서 푼 문제..

문제

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

코딩테스트 연습 - 다리를 지나는 트럭

본인 작성 답안 (비 효율적 list사용)

def solution(bridge_length, weight, truck_weights):
    current_BT = [0] * bridge_length       
    current_BW = 0
    answer = 0
    
    while len(current_BT):
        answer+=1
        leftout = current_BT.pop(0)       
        current_BW-=leftout
        if truck_weights:
            if current_BW + truck_weights[0]  <= weight:
                current_BW+= truck_weights[0]
                current_BT.append(truck_weights.pop(0))
            else:
                current_BT.append(0)
    return answer
print(solution(2,10,[7,4,5,6]))

다리위의 트럭 무게를 구할 때 sum 내장함수를 이용했는데

테스트 케이스에 시간초과로 걸려서 pop시키는 트럭무게들만 넣어서 비교했다.

 

위의 방식대로하면 시간복잡도가 커서 손해를 본다.

list가 아닌 deque를 이용해 풀어야 한다. 

봐줄만한 답안(?)

from collections import deque
def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights)
    current_BT = deque([0 for _ in range(bridge_length)])     
    current_BW = 0
    answer = 0
    
    while len(current_BT):
        answer+=1
        leftout = current_BT.popleft()       
        current_BW-=leftout
        if truck_weights:
            if current_BW + truck_weights[0]  <= weight:
                current_BW+= truck_weights[0]
                current_BT.append(truck_weights.popleft())
            else:
                current_BT.append(0)
    return answer

위의 list를 이용하는 것보다 약 6배 더 빠르더라... 통과 (67.35ms, 10.1MB)

deque의 시간복잡도는 O(1) 인데 list는 O(N) 이니까 list를 쓰면 효율성 측면에서는 꽝이다.