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

프로그래머스 스택/큐

# 다리를 지나는 트럭 (Level2)

• 앞 쪽에 위치한 트럭이 우선적으로 다리를 건너야 하기 때문에 FIFO 구조
• 리스트의 pop(0)은 0(n)의 시간복잡도를 가지고 deque의 popleft()는 O(1)의 시간복잡도를 가지기 때문에 deque사용한다
• 1초가 지날때마다 현재 다리에 있는 트럭의 무게와 다음으로 올라갈 트럭의 무게의 합이 최대 하중을 넘는지 확인한다
• 하중을 넘지 않는다면 다음 트럭을 올리고
• 그렇지 않다면 0을 더해 다리를 왼쪽으로 밀어낸다

 

- 첫번째 풀이(실패)

• Point. 하나의 테스트케이스에서 시간초과가 났다 -> sum이 O(n)이라 시간초과 발생

 

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_q = deque(truck_weights)
    q = deque([0] * bridge_length)
    
    while q:
        time += 1
        q.popleft()
        if truck_q:
            if sum(q) + truck_q[0] <= weight:
                q.append(truck_q.popleft())
            else:
                q.append(0)
    
    return time

 

- 두번째 풀이 (성공) -> sum대신 다리의 무게를 따로 관리해준다

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_q = deque(truck_weights)
    q = deque([0] * bridge_length)
    t_weight = 0 # 현재 다리의 무게
    
    while q:
        time += 1
        # 나갈 트럭이 있다면 그 무게를 빼준다
        if q[0] != 0: t_weight -= q[0]
        q.popleft()
        if truck_q:
            # 다리의 무게와 대기하는 트럭의 크기가 weight값을 넘지 않으면 더해준다
            if t_weight + truck_q[0] <= weight:
                t_weight += truck_q[0]
                q.append(truck_q.popleft())
            else:
                q.append(0)

    return time

 

* 시간복잡도를 생각하는 습관을 길러야겠다

wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki