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

[프로그래머스] 다리를 지나는 트럭 🛻 바로가기

아이디어

• 다리길이만큼 deque을 만들어서 트럭이 한 칸씩 왼쪽(←) 방향으로 움직인다.
  예를 들어

  걸린 시간	다리를 지난 트럭	다리를 지나고 있는 트럭	대기중
  0초	[]	[0, 0]	[7, 4, 5, 6]
  1초	[]	[0, 7]	[4, 5, 6]
  2초	[]	[7, 0]	[4, 5, 6]
  3초	[7]	[0, 4]	[5, 6]
  4초	[7]	[4, 5]	[6]
  5초	[7, 4]	[5, 0]	[6]
  6초	[7, 4, 5]	[0, 6]	[]
  7초	[7, 4, 5]	[6, 0]	[]
  8초	[7, 4, 5, 6]	[0, 0]	[]

해결방안

• 한 칸씩 왼쪽으로 이동하는 것을 어떻게 구현해야 될지 모르겠었다.
  -> 그냥 [0, 0] 에서 0번째 값을 빼준다. (popleft())

새로 알게 된 것

1. pop(0) vs popleft() 시간 복잡도

   • list.pop(0) - O(n)
   • deque.popleft() - O(1)

2. sum()의 시간복잡도는 O(n) -> 생각보다 오래 걸린다. (시간초과)

시간 복잡도

• O(n) (n == 트럭의 수)

코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0] * bridge_length)
    truck_weights = deque(truck_weights)
    
    current_weight = 0 # 현재 다리위에 있는 트럭들의 무게
    
    # 다리를 다 지날때까지 반복
    while len(bridge):
        # 한칸씩 땡기기(<-)
        current_weight -= bridge.popleft()
        
        # 대기중인 트럭이 있다면
        if truck_weights:
            # 다리에 지날 수 있으면 빼기
            if current_weight + truck_weights[0] <= weight:
                current_weight += truck_weights[0] 
                bridge.append(truck_weights.popleft())
            # 같이 지날 수 없으면 대기
            else:
                bridge.append(0)
        
        # 시간
        answer += 1
    
    return answer