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

[프로그래머스] 고득점 Kit 스택/큐 - 다리를 지나는 트럭

 

< 문제 >

 

< 풀이 > 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    queue<pair<int, int>> m_QReadyTruck;
    queue<pair<int, int>> m_QMovingTruck;

    int curWeight = 0;
    
    for (int i=0; i< truck_weights.size(); i++)
    {
        m_QReadyTruck.push(make_pair(truck_weights[i], 0));
    }

    while (!m_QReadyTruck.empty() || !m_QMovingTruck.empty())
    {
        answer++;

        if (!m_QReadyTruck.empty() && (curWeight + m_QReadyTruck.front().first) <= weight)
        {
            pair<int, int> curTruck = m_QReadyTruck.front();
            curTruck.second = answer;
            m_QMovingTruck.push(curTruck);
            curWeight += curTruck.first;
            m_QReadyTruck.pop();
        }

        if (bridge_length <= (answer - m_QMovingTruck.front().second + 1))
        {
            curWeight -= m_QMovingTruck.front().first;
            m_QMovingTruck.pop();
        }    
    }
    answer++;
    
    
    return answer;
}

 

< 해설 >

pair<int,int> 를 원소로 가지는 queue를 2개 사용하여 문제를 풀었다.

큐 1 은 준비중인 트럭을 가지는 큐, 큐2는 지금 이동중인 트럭을 가지는 큐 로 두었다.

 

원리는 현재 다리 위에 올라가 있는 중량을 비교하여 중량이 초과하지 않는다면 큐2에 트럭을 계속 넣어주는 방식이다.

pair의 second 에는 트럭이 다리를 진입하는 시간을 넣었다. 트럭은 1초에 1씩 이동하므로 다리의 길이가 10 일 때, 현재 시간이 11초, 큐2 front 에 들어있는 트럭이 1초에 다리에 진입했다면 다리를 완전히 지났다고 할 수 있다.

 

그런데 선두에 있는 트럭이 다리를 완전히 빠져나감과 동시에 다음 트럭이 다리에 진입할 수 있다. 코드상에서는 트럭이 다리를 벗어나기 직전에 트럭을 빼줘야한다.

 

그러므로 코드는

다리의 길이가 10, 현재 시간이 10, 선두 트럭이 1초에 진입했을시에 선두의 트럭을 빼줘야 코드가 정상작동한다. 따라서 다리의 길이 <= (현재시간 - 트럭이 진입한 시간 +1) 을 조건으로 주고 이동중인 트럭을 pop 해준다.