프로그래머스 - 다리를 지나는 트럭 - Level 2

문제

풀이전략

1. 이 문제에서 조건은 크게 무게와 시간, 트럭의 길이를 알아야한다. 최단 시간을 만들려면 최대한 많은 양의 트럭을 건너게 해야한다.
2. 다리에 올라가 있는 트럭을 큐에 넣어주고, 트럭 무게의 총합을 변수에 저장, 길이의 총합은 큐의 사이즈, 이것들을 이용하여 문제를 해결해준다.

코드

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int time = 0;
    queue<pair<int ,int> > q;
    int i = 0;
    int weightSum = 0;
    while(1){
    	// 트럭이 올라설때 마다 시간을 증가시켜준다. 
        time++;  
        // pair의 첫번째에는 차의 무게, 두번째에는 들어온 시간을 저장한다. 
        
        if(!q.empty()){
            pair<int, int> ret = q.front();
            // 트럭이 나가야 할 시간이면 pop해준다. 
            if(time - ret.second >= bridge_length){
                q.pop();
                weightSum -= ret.first;    
                printf("%d %d %d\n",ret.first, ret.second,time);
            }    
        }
        
        if(q.empty() && i == truck_weights.size()) break;
        // truck을 도로에 추가할 수 있을때
        if(i < truck_weights.size() && (weightSum + truck_weights[i] <= weight) && q.size() < bridge_length){
            // 트럭 무게합을 구해준다.
            weightSum += truck_weights[i];
            // 시간과 무게를 pair형으로 넣어준다.
            q.push(make_pair(truck_weights[i], time));
            // i를 증가시켜 다음 트럭을 확인한다. 
            i++;
        }
        
        
    }
    
    return time;
}

소감

시간과 같이 비교해가면서 큐에 넣고 값을 찾아가는 과정이 인상적이였다. 문제를 풀때 시간을 맞추는것이 너무 힘들었다. 잘 집중해서 다시한번 복습하자.