[스택/큐, 난이도 중하] 프로그래머즈, 다리를 지나는 트럭

트럭은 1초에 최대 1번 다리에 들어올 수 있고, 최대 1번 나갈 수 있다.

즉 초를 세는 변수를 만들고, 반복문 안에 트럭이 다리에 들어오는 조건문과 나가는 조건문을 하나씩 세워주면 된다.

제일 앞에 있는 트럭의 입장 시각이 현재 시각에 다리의 길이를 뺀 값이 되면, 누적 무게에서 이 트럭의 무게를 빼고 queue에서 pop시켜주고

누적 무게에 가장 앞에 대기중인 트럭의 무게를 더해봐서, 제한 무게를 넘어가지 않는다면 queue에 push 해주면 된다.

queue 안에 들어있는 pair 정보는 트럭의 무게와 입장 시각이다.

 

테스트 케이스 14개 모두 통과

 

#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 1; //현재 초
    queue<pair<int, int> >q; //무게,입장 시각 pair
    q.push(make_pair(truck_weights[0],1)); //첫 트럭 push
    int current_weight=truck_weights[0]; //누적 무게
    int trucknum=1; //맨 앞에 대기중인 트럭 번호
    while(!q.empty()){
        if(q.front().second<=time-bridge_length){ //나가는 트럭
            current_weight -= q.front().first;
            q.pop();
        }
        if(trucknum<=truck_weights.size()-1){ //들어오는 트럭
	        if(truck_weights[trucknum]+current_weight<=weight){
	            q.push(make_pair(truck_weights[trucknum],time));
	            current_weight += truck_weights[trucknum];
	            trucknum++;
	        }
        }
        time++;
    }
    return time-1;
}