프로그래머스 / 다리를 지나는 트럭

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

프로그래머스

    queue<pair<int, int>> qBridge;

queue<pair<int,int>>를 사용하여 다리의 <차량무게,진입시간>을 저장했다

    int vIdx = 0;

다리위의 전체 차량 무게를 별도의 int로 관리하여 매 틱마다 새로 계산하지 않도록 했다

 

    do{
        time++;

        // 차량이 다리에 올라온 시간 + 다리의 길이 <= 현재 시간인 경우 차량 통과
        if (!qBridge.empty() && bridge_length + qBridge.front().second <= time)
        {
            // 현재 무게 갱신
            curWeight -= qBridge.front().first;
            // 차량 통과
            qBridge.pop();
        }

        // 여유 공간과 무게가 있으면 차량 추가
        if (vIdx < truck_weights.size() && curWeight + truck_weights[vIdx] <= weight && bridge_length > qBridge.size())
        {
            curWeight += truck_weights[vIdx];
            qBridge.push({ truck_weights[vIdx],time });
            vIdx++;
        }
    }while(!qBridge.empty());

반복문으로 time을 증가시켜 현재 시간과 진입 시간을 비교하여 다리를 모두 건넌 차량을 큐에서 제거했다. 이때 다리가 비어있으면 차량을 제거하는것을 방지해 빈 큐에 대한 접근을 방지했다

전체 차량 무게가 다음 트럭의 무게를 더해도 제한 무게인 wieght를 넘지 않고 다리 길이가 여유가 있는 경우에만 차량을 추가했다

각 차량은 큐에 한 번 들어가고 한 번 제거되므로 시간복잡도는 O(N)이다

 

#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>> qBridge;
    int vIdx = 0;
    int curWeight = 0;
    int time = 0;

    do{
        time++;

        // 차량이 다리에 올라온 시간 + 다리의 길이 <= 현재 시간인 경우 차량 통과
        if (!qBridge.empty() && bridge_length + qBridge.front().second <= time)
        {
            // 현재 무게 갱신
            curWeight -= qBridge.front().first;
            // 차량 통과
            qBridge.pop();
        }

        // 여유 공간과 무게가 있으면 차량 추가
        if (vIdx < truck_weights.size() && curWeight + truck_weights[vIdx] <= weight && bridge_length > qBridge.size())
        {
            curWeight += truck_weights[vIdx];
            qBridge.push({ truck_weights[vIdx],time });
            vIdx++;
        }
    }while(!qBridge.empty());

    answer = time;
    return answer;
}