[알고리즘C++]다리를 지나는 트럭

오늘의 문제

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

다리를 지나는 트럭

나의 풀이

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

using namespace std;

int solution(int bl, int weight, vector<int> truck_weights) {
    queue<pair<int, int>> inBridge;
    int nowWeight = 0;
    int num = truck_weights.size();
    int time =0;

    for(int i=0;i<num;i++){
        if(nowWeight + truck_weights[i] <= weight && inBridge.size() != bl){ // ok
            time++;
            if(inBridge.size()!= 0 && inBridge.front().second + bl == time){
                nowWeight -= inBridge.front().first;
                inBridge.pop();  
            }
            nowWeight += truck_weights[i];
            inBridge.push(make_pair(truck_weights[i], time));
        }else{
            int w = inBridge.front().first;
            int t = inBridge.front().second;
            inBridge.pop();
            nowWeight -= w;
            time = t+bl-1;
            i--;            
        }
    }  
    return time + bl;
}

모범 정답

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int tot_w = 0;
    int t_front = 0;
    int t_cur = 0;
    int sec = 0;
    queue <int> q;

    while (t_front != truck_weights.size()) {
        if (!q.empty() && (sec - q.front() == bridge_length)) {
            tot_w -= truck_weights[t_front];
            ++t_front;
            q.pop();
        }
        if (t_cur != truck_weights.size() && tot_w + truck_weights[t_cur] <= weight) {
            tot_w += truck_weights[t_cur];
            ++t_cur;
            q.push(sec);
        }
        ++sec;
    }
    answer = sec;
    return answer;
}

배울 점

• queue를 사용한 점은 같았다.
• 모든상황을 고려해보는것이 쉽지 않다. 문제를 풀면서 queue에서 빼줘야 할 상황을 그냥 지나쳐 버리는 바람에 시간이 오래 걸려버렸다. 뭐가를 처리해줘야 한다면, 그 상황이 처할 모든 상황을 고려할 수 있어야겠다.