[문제풀이] 다리를 지나는 트럭

📢 문제

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

📢 알고리즘

큐

📢 풀이

• 각 원소가 큐에 들어있던 시간 = 현재시각 - 큐에 들어온 시각
  • 큐에 들어있던 시간이 원소마다 제각각 다르고 시간은 계속 흐르니까 큐에 들어온 시각을 따로 저장
  • queue<pair<무게,큐에들어온시각>>으로도 됨

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0; //현재시간
    int idx = 0; //배열 index
    int sum = 0; //큐 무게 합
    
    queue<int> q1; //무게 큐
    queue<int> q2; //들어온 시간 큐
    
    answer++;
    q1.push(truck_weights[idx]);
    sum += truck_weights[idx];
    q2.push(answer);
    idx++;
    
    while(!q1.empty()) {
        answer++;
        if(!q1.empty() && answer - q2.front() == bridge_length) { //큐에서 빼기
            int w = q1.front();
            q1.pop();
            q2.pop();
            sum -= w;
        }
        if(idx < truck_weights.size() && q1.size() < bridge_length 
           && truck_weights[idx] + sum <= weight) 
        { //큐에 넣기
            q1.push(truck_weights[idx]);
            sum += truck_weights[idx];
            q2.push(answer);
            idx++;
        }
        
    }
    return answer;
}