프로그래머스 스택큐_다리를지나는트럭 문제

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다.

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.

트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다.

이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 사항

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

| bridge_length | weight | truck_weights | return| |—| — | — | —| |2| 10 | [7,4,5,6] | 8| |100| 100 | [10] | 101| |100| 100 | [10,10,10,10,10,10,10,10,10,10] |110|

문제 풀이

def solution(bridge_length, weight, truck_weights):
    ing_truck = []
    answer = 0
    now_weight = 0

    while ing_truck or truck_weights:
        for i in ing_truck:
            i[1]+=1

        if ing_truck and ing_truck[0][1]==bridge_length:
            now_weight-=ing_truck[0][0]
            ing_truck.pop(0)
            
        if  truck_weights and truck_weights[0]+now_weight<=weight:
            new_truck = truck_weights.pop(0)
            ing_truck.append([new_truck,0])
            now_weight+=new_truck
        answer+=1
        
    return answer

• 큐를 이용한 문제
• now_weight = 현재 다리 위 무게
• ing_truck = 다리위를 지나고있는 트럭의 무게와 경과시간
• new_truck = 새로 다리에 들어갈 트럭
• 대기중인 트럭, 다리 위를 지나고있는 트럭이 모두 없을때 까지 반복
• 다리 위 트럭의 경과시간이 다리의길이와 같아지면 지나간것으로 판단하여 pop(), 현재 다리 위 무게를 갱신해준다.
• 다음 대기중인 트럭이 다리위에 추가되어도 괜찮으면 ing_truck에 push
• 시간 증가

참고 : https://programmers.co.kr/learn/courses/30/lessons/42583