[프로그래머스/Level 2] 다리를 지나는 트럭 (C++)

programmers.co.kr/learn/courses/30/lessons/42583

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

 

1. 큐 ready를 선언하고, truck_weight의 원소들을 모두 push
2. 다리를 건너는 트럭을 나타내는 pair형 벡터 onBridge를 선언 (트럭의 무게와 이동거리 저장)
3. 현재 다리 위에 있는 트럭의 무게 합과 큐의 front() 값이 weight의 무게보다 작거나 같은지 비교
   (이때 앞에 큐가 비어있는지 반드시 확인)

4. onBridge 벡터의 크기만큼 onBridge 모든 원소들의 second 값을 1증가 (거리 1 이동)
5. 이동을 했으므로 경과 시간 1 증가
6. onBridge 맨 앞 원소의 second값이 bridge_length와 같다면, 현재 다리 위에 있는 무게에서 first값을 빼주고, erase를 통해 원소 제거
7. 위의 과정을 계속 반복하다가 ready 큐와 onBridge 벡터가 둘다 비게되면 무한루프 종료

 

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 1, sum = 0; // 경과 시간, 현재 다리 위 무게
    queue<int> ready; // 대기 트럭
    vector<pair<int, int> > onBridge; // 다리를 건너는 트럭
    
    for(int i = 0; i < truck_weights.size(); i++) {
        ready.push(truck_weights[i]);
    }
    
    while(1) {
    	// 종료 조건
        if(ready.empty() && onBridge.empty()) break;
        
        // 현재 다리 위에 있는 트럭의 무게 + 들어올 트럭 무게 <= 버티는 무게
        if(!ready.empty() && sum + ready.front() <= weight) {
            sum += ready.front();
            onBridge.push_back({ready.front(), 0});
            ready.pop();
        }
        
        // 현재 다리 위에 있는 트럭 1칸씩 이동
        for(int i = 0; i < onBridge.size(); i++) {
            onBridge[i].second++;
        }
        
        // 시간 경과
        answer++;
        
        // 맨 앞에 있는 트럭이 다리를 빠져나갈 때
        if(onBridge[0].second == bridge_length) {
            sum -= onBridge[0].first;
            onBridge.erase(onBridge.begin());
        }
    }
    
    return answer;
}