[Algorithm] 프로그래머스 C++ : 다리를 지나는 트럭

 

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

코딩테스트 연습 - 다리를 지나는 트럭

되게 헤맸던 문제..

그냥 봤을땐 쉬워보이는데 큐에 넣으면서 초를 세는게 헷갈린다.

 

첫번째 포인트는, while(1)을 해놓고 다리에 올라갈 수 없는 트럭이 나오면

그냥 0을 큐에 삽입해서 초가 증가할 수 있게 해주는 것!

 

두번째 포인트는, 다리에 올라갈 수 있는 트럭이 꽉 차서 큐의 맨 앞 트럭을 뺌과 동시에

다리에 올라가 있는 총 트럭의 무게가 감소하고 그와 동시에 다시 새로운 트럭이 삽입된다!!

 

break의 조건은 트럭의 인덱스인데

다 삽입됐을 때, 마지막 트럭은 이제 막 다리에 올라온 것이므로

bridge_length만큼 초를 더해줘야 한다.

 

 

Code

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

using namespace std;

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