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

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

접근

오랜만에 삼성 스타일의 시뮬레이션 문제 같았습니다.

주의해야 할 점은 10000의 길이와 10000의 무게를 견딜수 있는 다리를

10000의 무게를 가진 트럭 10000대가 지나갈 때, 한번에 하나의 트럭만 지나갈 수 있으므로

최대 걸리는 시간은 약 10000 * 10000 = 1억초 가 됩니다.

진짜 시뮬레이션처럼 시간을 1씩 증가시키면서 1억번 돌리면.. 아무래도 시간초과가 날 것 같습니다.

구현

다리가 더이상 무게를 견딜 수 없을 때만, 맨 앞에 가는 트럭이 하차하는 시간으로 타임워프 하는 방식이며

해당 시간에 무엇을 먼저 해주어야 하는지, 선후 관계만 잘 따지면 됩니다.

• 시간은 1초부터 시작합니다.

1. 현재 시간에 하차 해야 할 트럭이 있는지 먼저 살펴봅니다.
2. 다리에 대기 중인 가장 최근 트럭을 올릴 수 있는지 판단합니다.
   2-1. 올릴 수 있다면 승차 시키고, 시간을 1 증가시킵니다.
   2-2. 올릴 수 없다면 가장 먼저 하차해야 할 시간으로 타임워프 합니다.

위 알고리즘으로 진행하면 1억초가 걸리는 케이스에서도 루프를 1억번 돌지 않고, 10000번 정도 돌게 됩니다.

그리고 대기하는 트럭이 queue의 방식으로 빠져나오는것 같지만, 굳이 벡터로 주어진 데이터를 큐나 덱으로 바꾸거나, 역으로 돌리시지 말고 index를 나타내는 변수 하나만 선언하시면 됩니다.

다음은 코드 전문입니다.

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 1;
    int loaded_weight = 0;
    int load_target_num = 0;
    
    queue<pair<int,int> > bridge;
    
    
    
    do{
        if (!bridge.empty()) {
            if (bridge.front().second == time) {
                loaded_weight -= bridge.front().first;
                bridge.pop();
            }
        }
        
        if ((loaded_weight < weight) && ((weight-loaded_weight) >= truck_weights[load_target_num]) && load_target_num < truck_weights.size()) { // load available
            
            bridge.push(pair<int, int>( truck_weights[load_target_num] , time+bridge_length ));
            loaded_weight += truck_weights[load_target_num];
            load_target_num++;
            time++;
        }else if(!bridge.empty()){ //load unavailable
            time = bridge.front().second;
        }
        
    }while((load_target_num < truck_weights.size()) || !bridge.empty());
    
    return time;
}