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

✅ 문제

✅ 코드

1. 정답률 28.6

from collections import deque

def solution(bridge_length, weight, truck_weights):
    dq = deque(truck_weights)
    length = 1
    time = 1
    item = dq.popleft()
    while dq:
        if item + dq[0] <= weight and length <= bridge_length:
            item += dq.popleft()
            length += 1
            time += 1
        else:
            item = dq.popleft()
            length = 1
            time += bridge_length
    return time + bridge_length

2. 다른 사람의 코드

def solution(bridge_length, weight, truck_weights):
    time = 0
    q = [0] * bridge_length
    while q:
        q.pop(0)
        time += 1
        if truck_weights:
            if sum(q) + truck_weights[0] <= weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return time

☑️ 해설

  구글링 결과 모든 사람들이 1초씩 계산해야 풀린다고 한다... 애초에 1초 아니면 다리 길이만큼의 시간이 지나게 풀었으니 계속 틀렸던 것. 하긴 다리 위의 무게가 최대 무게보다 가벼워지는 순간 다시 트럭이 지나갈 수 있으니 1초씩 계산하는게 맞긴하다.

q = [0] * bridge_length

다리 길이 만큼의 0을 가진 리스트를 만든다. 리스트의 0의 개수는 다리의 길이다.

while q:
    q.pop(0)
    time += 1
    if truck_weights:
        if sum(q) + truck_weights[0] <= weight:
            q.append(truck_weights.pop(0))
        else:
            q.append(0)

리스트의 0번 인덱스가 1개 빠질 떄마다 1초 증가한다. 빠진 자리에는 트럭이 추가되거나 0이 추가된다.

1. 트럭이 추가되는 경우
   다리 위의 무게(sum(q) + truck_weights[0])가 최대 무게(weight)보다 가볍거나 같다.
2. 0이 추가되는 경우
   다리 위의 무게(sum(q) + truck_weights[0])가 최대 무게(weight)보다 무겁다.

만약 weight = 10, bridge_length = 2, truck_weights = [7,4,5,6] 인 경우에 트럭[7]이 지나갈 때까지 다음 트럭이 리스트 안에 들어갈 수 없다

0 0 (time = 0)
0 7 (1s)
7 0 (2s)
0 4 (3s)
4 5 (4s)
5 0 (5s)
0 6 (6s)
6   (7s)
    (8s)
break