[programmers/Lv.2] 다리를 지나는 트럭

❓  문제

다리를 지나는 트럭

 

🛎️  아이디어

1. bridge 길이 만큼의 deque를 생성한다.
   
   
2. 모든 트럭이 다리에 올라갈 때까지 while문을 돈다.
   
   
3. bridge에서 popleft를 통해 한 칸 씩 왼쪽으로 옮겨간다. (rotate와 다름. rotate는 1->2->3->1 처럼 돌기 때문)
   
   
4. 새롭게 들어갈 트럭의 무게와 현재 bridge의 무게를 더해서 견딜 수 있는지 확인한다.
   • 견딜 수 있다면 새롭게 들어갈 트럭의 무게를 더하고
   • 견딜 수 없다면 0을 더한다.

 

💻  풀이

# 최대 bridge_length대 올라갈 수 있음. (다리의 길이)
# weight만큼 버틸 수 있음.
# 다리에 완전히 오르지 않았다면 무게를 무시한다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0

    # 현재 올라간 트럭의 무게 합
    weight_sum = 0

    # bridge 크기만큼의 데큐 생성
    bridge = deque([0 for i in range(bridge_length)])
    while truck_weights:
        time += 1
        weight_sum -= bridge.popleft()

        # 이번에 들어갈 트럭 무게 계산
        truck = truck_weights[0]
        if weight_sum + truck <= weight:
            weight_sum += truck
            bridge.append(truck_weights.pop(0))
        else:
            bridge.append(0)

    # 마지막 트럭이 들어간 후 완전히 나올 때 까지의 시간 더해주기 (bridge_length)
    return time + bridge_length

 

🧩  포인트

- deque를 사용해서 popleft, append로 실제 다리를 건너는 것처럼 한다.

- 처음에 현재 bridge의 무게를 구할 때 sum() 함수를 사용했는데, 이럴 경우 시간 초과가 나기 때문에 sum을 담을 변수를 생성한 후 계산을 해줘야 한다.