[프로그래머스 lv2] 다리를 지나는 트럭 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

다리의 길이 bridge_length, 최대 수용 무게 weight가 주어졌을 때, 모든 트럭을 이동시키기 위한 최소 시간을 구하는 문제이다.

다리에 올라온 트럭은 먼저 올라온 순서대로 다리를 빠져나간다. 따라서 다리를 queue로 표현하면 큐의 앞쪽에서 트럭을 제거하고 뒤쪽에 새로운 트럭을 추가함으로써 간단하게 이동 상태를 표현할 수 있다.

 

queue의 길이가 bridge_length와 같을 때  가장 앞쪽에 있는 트럭이 다리를 빠져나가므로 이를 큐에서 제거한다.

현재 다리에 있는 트럭의 총 무게와 새로운 트럭 무게의 합이 주어진 weight 보다 작거나 같다면 새로운 트럭을 queue에 추가한다.

queue는 배열과 다르게 길이가 보장되지 않으므로, 새로운 트럭이 다리에 올라가지 못할 때는 queue에 0을 추가하여 트럭 사이의 간격을 맞추어주자.

 

주어진 트럭이 모두 다리에 올라갈 때까지의 위의 과정을 반복한다.

트럭이 모두 다리에 올라갈 때까지의 시간을 t라고 했을 떄, 모든 다리가 빠져나오는 시간은 t+(마지막 트럭이 빠져나올 때까지의 시간)이다.

마지막 트럭이 다리에 올라간 후 빠져나올 때까지의 시간은 bridge_length 이므로 t+bridge_length를 리턴하면 정답이다. 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    
    int bn = bridge_length;
    int tn = truck_weights.size();
    
    queue<int> q;
    int t = 0, sum = 0, idx = 0;
    
    while (idx < tn) {
        
        if (q.size() == bn) {
            sum -= q.front();
            q.pop();
        }
        
        int tmp = truck_weights[idx];
        if (sum+tmp <= weight) {
            q.push(tmp);
            sum += tmp;
            idx++;
        }
        else q.push(0);
        t++;
    }
    return t+bn;
}