다리를 지나는 트럭

📖 스택/큐 > 다리를 지나는 트럭

📖What I thought

1. 대기 순서대로 다리를 지나갈 수 있음 → FIFO → queue
2. 다음 두 조건을 만족 시 트럭 올리기 가능
   • 현재 다리 위의 트럭 무게 + 대기 순서 1번 트럭 ⇐ 최대 무게
   • 다리 위에 있을 수 있는 최대 트럭 수 ⇐ 현재 다리에 있는 트럭 수
3. 근데 그러면 트럭이 다리를 다 지난 건 어떻게 알지…? queue의 길이를 다리 길이만큼 0으로 채워넣자!!
4. 대기 트럭이 못 들어가는 상황일 때마다도 0으로 채워줘서 다리 길이 유지
5. 대기 트럭이 없으면 3~4번 과정 건너뛰기 but loop는 돌려줘야 함 왜냐? → 대기 트럭은 없어도 다리를 지나는 중인 트럭 있을 수 있잖아

📖풀이

📎Queue

def solution(bridge_length, weight, truck_weights):
    bridge = [0 for _ in range(bridge_length)]
    truck_sum = 0
    sec = 0
    
    while bridge:
        sec += 1
        fin = bridge.pop(0)
        truck_sum -= fin
        
        # 대기 트럭X 다리를 건너는 트럭만 있는 상황
        if not truck_weights:
            continue
            
        #다리 위에 트럭 올려
        if truck_sum + truck_weights[0] <= weight:
            truck = truck_weights.pop(0)
            bridge.append(truck)
            truck_sum += truck
        else:
            bridge.append(0)
            
    return sec

sec : 소요 시간 bridge : 다리 상황 truck_sum : 다리 위 트럭의 무게

• 처음엔 다리 위의 트럭의 무게를 그 때 그 때 sum()으로 구했는데 타임 오버 T_T → 아무래도 그 때마다 O(n)만큼 더 돌아야 하니까 그런 듯 → 그래서 변수를 하나 두고 변하는 트럭 무게만 +- 해줌

📎Deque

from collections import deque
def solution(bridge_length, weight, truck_weights):
    bridge = deque([0 for _ in range(bridge_length)])
    truck_weights = deque(truck_weights)
    
    truck_sum = 0
    sec = 0
    
    while bridge:
        sec += 1
        fin = bridge.popleft()
        truck_sum -= fin
        
        if not truck_weights:
            continue
        
        if truck_sum + truck_weights[0] <= weight:
            truck = truck_weights.popleft()
            bridge.append(truck)
            truck_sum += truck
        else:
            bridge.append(0)
            
    return sec

• 위 코드에서 queue를 deque로 바꾼 코드 (bridge,truck_weights)
• 위 코드보다 속도가 훠어얼씬 빨랐다

📖What I learned

1. 길이를 유지해야 하는 상황일 때는 0과 같은 기본 값을 넣어서 길이를 유지해주자
2. queue를 사용할 때는 확실히 deque()가 훠어얼씬 빠르다

list.pop(0) : O(n) deque.popleft() : O(1)

📖관련 지식

📎Queue

📎Deque