[큐] 다리를 지나는 트럭

코딩테스트 연습 - 다리를 지나는 트럭

from collections import deque
 
def solution(bridge_length, weight, truck_weights):
    answer = 0
    v = 0
    tot = 0  # sum()을 사용하면 testcase5 에서 시간초과
    bridge = [0] * bridge_length
 
    q = deque(bridge)
    trucks = deque(truck_weights)
 
    while trucks:
        # 트럭이 다리를 건넜을 경우 v 는 != 0
        if v != 0:
            if tot + trucks[0] <= weight: 
                q[0] = trucks.popleft()
                tot += q[0]
 
        while trucks and tot + trucks[0] <= weight:
            new = trucks.popleft()
            tot += new
            q.appendleft(new)
            l = q.pop()
            tot -= l
            answer += 1
 
        v = q.pop()
        q.appendleft(0)
        tot -= v
        answer += 1
 
    # index = 도착지와 가장 멀리 떨어져 있는 트럭의 위치
    # 그 트럭이 끝까지 가면 모든 트럭이 도착한 것이다.
    for i, j in enumerate(q):
        if j != 0:
            index = i
            break
 
    plus = bridge_length - index
    answer += plus
    return answer
 
bridge_length = 2
weight = 10
truck_weights = [7, 4, 5, 6]
print(solution(bridge_length, weight, truck_weights))

q = deque([0, 0])
7	0	pop 1번
0	7	pop 2번
0	0	pop 2번
4	0	pop 3번
5	4	pop 4번
0	5	pop 5번
0	0	pop 5번
6	0	pop 6번
0	6	pop 7번

7과 5가 다리를 건널 때, 다리는 [0, 0]으로 초기화 된다. 이 때, 바로 아래의 while문으로 들어간다면 q.pop()을 한번 더 하게 된다. 이 경우 q[0]에 새로운 트럭을 추가시키고 while문으로 내려가게 한다.