Programmers - 다리를 지나는 트럭

---

title: Programmers - 다리를 지나는 트럭
date: 2022-06-23
tags:

• Algorithm

---

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

문제 요약

트럭의 무게와 다리의 최대 하중, 다리의 길이가 주어진다. 트럭이 순서대로 모두 건너기까지의 시간을 구해 return한다.

문제 풀이

queue를 이용하면 쉽다. 현재 다리의 하중을 계산하기 위한 트럭의 무게, 그리고 트럭이 진입한 시각을 pair로 묶어 queue에 넣는다.
각 loop의 처음에 pop을 할 수 있다면 pop을 해준다. 이후 트럭이 더 지나갈 수 있다면 다리에 진입시키고, 안 된다면 가장 선두의 트럭이 도착하는 시간으로 시각을 지정해준다.
바로 시각을 지정해주는 이유는 다리의 길이가 max인 10k이고, 트럭이 다리의 하중을 전부 차지하여 해당 트럭이 지나가기만 기다려야 하는 상황이라 가정하자.
시각을 1씩 늘리면 10k의 loop를 기다려야 한다. 이를 위해 트럭이 올라가지 않고 1이라도 지나면 바로 선두의 트럭이 내려가도록 처리하는 것이 빠르다.

프로그램

#include <vector>
#include <queue>
#include <utility>

using std :: vector ;
using std :: queue ;
using std :: pair ;
using std :: make_pair ;

int solution ( int bridge_length , int weight , vector < int > truck_weights )
{
    int answer = 1 ;
    int iCnt = 0 ;
    int iCurrentWeight = 0 ;
    int iLen = truck_weights.size () ;
    int * ipTemp = truck_weights.data () ;
    int iIndex = 0 ;
    queue < pair < int , int > > qCheck ;            // < weight , start time >



    while ( iCnt < iLen )
    {
        if ( ( ! qCheck.empty () ) && ( bridge_length + qCheck.front ().second == answer ) )
        {
            iCurrentWeight -= qCheck.front ().first ;
            qCheck.pop () ;
            ++ iCnt ;
        }

        if ( iCnt == iLen )
            return answer ;

        if ( ( iIndex != iLen ) && ( iCurrentWeight + ipTemp [ iIndex ] <= weight ) )        // If can load the truck to bridge
        {
            qCheck.emplace ( make_pair ( ipTemp [ iIndex ] , answer ) ) ;
            ++ answer ;
            iCurrentWeight += ipTemp [ iIndex ++ ] ;

            continue ;
        }

        // If can't load new truck, need to unload the truck
        answer = qCheck.front ().second + bridge_length ;
    }
}