스택/큐 - 다리를 지나는 트럭

https://www.welcomekakao.com/learn/courses/30/lessons/42583

 

위 문제를 풀기위해 특별한 로직은 없는 것 같고, 아래에 코드풀이와 염두해두어야 할 점들을 적어놓았다.

 

1. 다리를 건너는 트럭을 계산하기 전에 다리를 지나는 트럭을 계산하여야한다. (예제 경과시간 3초를 보고 알 수 있듯이 다리를 지난 트럭을 먼저 계산한 후에, 다리를 건너는 트럭을 계산해야 한다.)

2. 다리를 오른 후 다리를 지날 때까지 시간의 흐름을 어떻게 계산해야하는 지 고민을 했었는 데, 27 line 의 계산을 떠올렸다.

3. 다리를 건너는 트럭을 구할 땐, 현재무게, 올라 탈 트럭의 무게와 다리가 견딜 수 있는 무게를 잘 연산하면 된다 (36 line ). 그리고 2번째 비교인 다리의 길이도 염두해두어야 한다.

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int curIndex = 0;
    int sumWeight = 0;
    int size = truck_weights.size();
    // 다리를 건넌 트럭의 수
    int finish = 0;
    
    // 다리를 건너는 트럭
    queue<pair<int, int>> q; // pair -> [다리에 온 시간, 트럭의 무게]
 
    while (size != finish) {
        answer++;
        
        // 예제를 보면 3초에 무게가 7인 트럭이 빠지고, 4인 트럭이 다리에 오르므로
        // 다리를 지난 트럭을 구하는 연산을 한 후 다리를 건너는 트럭을 계산 해야함.
        /** 1. 다리를 지난 트럭 **/
        if (!q.empty()) {
            pair<int, int> p = q.front();
            // 다리에 온 시간 + 다리의 길이 => 다리에 다 건넜는 지 아닌 지 판별가능
            if (p.first + bridge_length == answer) {
                finish++;
                sumWeight -= p.second;
                q.pop();
            }
        }
        
        /** 2. 다리를 건너는 트럭 **/
        int curTruckWeight = truck_weights[curIndex];
        if (sumWeight + curTruckWeight <= weight && q.size() < bridge_length) {
            sumWeight += curTruckWeight;
            curIndex++;
            q.push({answer, curTruckWeight});
        }
    } 
    
    return answer;
}