[Python]프로그래머스 - 다리를 지나는 트럭(level2)

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

from collections import deque


def solution(bridge_length, weight, truck_weights):
    answer = 1
    dq = deque()  # [트럭무게, 다리를 지난 시간]
    dq.append([truck_weights[0], bridge_length])
    truck_weights.pop(0)

    while len(dq) != 0 and dq[0][1] != 0:
        temp = 0  # 다리를 다 건넌 트럭
        total_weight = 0  # 현재 다리에 있는 트럭들의 총 무게

        # dq에 있는 트럭들의 시간 -1
        for i in range(len(dq)):
            total_weight += dq[i][0]
            dq[i][1] -= 1
            if dq[i][1] == 0:
                temp += 1

        # 다리를 다 건넌 트럭만큼 지우기
        for i in range(temp):
            total_weight -= dq[i][0]
            dq.popleft()

        # (현재 다리에 있는 트럭들 무게 + 대기트럭)이 다리 무게보다 작으면 다리에 추가!
        if len(truck_weights) != 0 and total_weight + truck_weights[0] <= weight:
            dq.append([truck_weights[0], bridge_length])
            truck_weights.pop(0)

        answer += 1

        # print(answer, dq, truck_weights)

    return answer

설명

우선 이 문제는 deque를 이용해서 풀었다. 왜냐하면 리스트의 원소를 앞뒤로 빼야하는 경우가 있기 때문이다.

deque에는 [트럭무게, 다리를 지난 시간]이 저장되어 있다. 시간이 경과할수록 다리를 지난 시간은 -1씩 줄어든다.

 

1. 가장 먼저, dq에 대기중인 트럭1을 넣어줬다. 그리고 대기중인 트럭 리스트에서 빼줬다. while문에 들어가기 전에 트럭을 넣었기 때문에 answer에 1을 더해줬다.

 

2. while문은 dq가 비어있지 않고 dq에 있는 트럭의 시간이 0이 될때까지 돈다.

 

while문 안

1. 다리위에 있는 모든 트럭의 남은 시간을 1씩 감소시킨다. 이때, 감소시킨 값이 1이면 temp의 값을 1씩 증가시킨다. (temp는 현재 시간에 다리 건너기를 완료한 트럭의 개수임)

 

2. temp만큼 for문을 돌리면서 완료된 트럭들을 total_weight에서 빼주고 dq에서도 빼준다.

 

3. (현재 다리에 있는 트럭들 무게 + 대기트럭)이 다리 무게보다 작으면 dp에 추가하고 대기 리스트에선 빼준다.