[Lv 2] 다리를 지나는 트럭

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

프로그래머스

 

이 문제는 queue를 사용하면 해결 할 수 있다.

 

큐 자료구조를 통해 현재 다리를 건너는 트럭들을 담아둔다.

queue에는 현재 다리를 건너는 트럭의 무게와 다리를 건너는데 필요한 시간을 담는다.

또한, 현재 다리를 건너고 있는 트럭들의 총 무게를 저장한다.

queue<pair<int, int>> q; // 트력 무게, 시간
q.push({truck_weights[0], bridge_length});
answer = 1;
now = truck_weights[0];

 

이후, 모든 트럭들이 다리를 건너 다리에 트럭이 없을 때 까지 시간 연산을 수행한다.

만약, 큐의 가장 앞쪽(다리에 먼저 접근한 트럭)의 필요 시간이 총 시간과 일치한 경우

큐에서 트럭을 제거하고, 총 무게에서 제거한 트럭의 무게를 뺀다.

if(q.front().second == answer){
    int qWeight = q.front().first;
    q.pop();
    now -= qWeight;
}

 

또한, 총 무게와 큐에 삽입할 트럭의 무게의 합이 다리의 제한 무게보다 작거나 같으면 다리에 트럭을 올린다.

다리에 트럭을 올릴때 트럭의 필요시간은 다리의 길이 + 현재 시간으로 한다.

if(idx<truck_weights.size() && now + truck_weights[idx] <= weight){
     now += truck_weights[idx];
     q.push({truck_weights[idx], bridge_length + answer});
     idx++;
}

 

위 방식으로 큐에 시간을 담는 이유는

큐는 iterator를 통해 순회할 수 없기 때문이다.

따라서 큐에 필요 시간을 모두 계산한 후 담고, 현재 시간이 필요 시간에 접근하면

큐에서 제거하는 방식을 사용한다.

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int now = 0, idx = 1;
    
    queue<pair<int, int>> q; // 트력 무게, 시간
    q.push({truck_weights[0], bridge_length});
    answer = 1;
    now = truck_weights[0];
    
    while(!q.empty()){
        if(q.front().second == answer){
            int qWeight = q.front().first;
            q.pop();
            now -= qWeight;
        }
        if(idx<truck_weights.size() && now + truck_weights[idx] <= weight){
            now += truck_weights[idx];
            q.push({truck_weights[idx], bridge_length + answer});
            idx++;
        }
        
        
        answer++;
    }
    
    return answer;
}