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

푸는 과정에서도 나와있듯 큐를 이용하는 문제였다. 

 

종료과정은 모든 트럭이 다리를 건넜을 경우이다. 그리고 다리가 견딜 수 있는 무게는 정해져 있기 때문에 모든 트럭이 줄지어서 다리를 건널 수 없다. 트럭이 다리를 건널때 견디는 무게를 넘어가면 그 트럭은 다른 트럭이 건널때 까지 기다리고 건너야한다. 

 

과정은 다음과 같다.

• 다리를 건너는 트럭 정보(트럭무게, 건너는 시간)를 담을 큐 컨테이너 q, 현재 다리에 가해지는 무게를 담을 정수형 변수 w, 다리를 건넌 트럭을 담을 벡터 컨테이너 v를 선언한다.

• w와 다리를 건널 트럭의 무게를 더했을때 다리가 견디는 무게보다 적다면 q에 트럭 정보를 담는다. 만약 더 무겁다면 다리가 견딜 수 없으므로 그 트럭은 대기해야 한다.

• 현재 진행된 시간과 q의 가장 앞에 있는 트럭 정보의 최초로 건넌 시간을 빼준다. 이 값이 다리 길이와 같다면 이 트럭은 다리를 건넌 것이므로 v에 트럭무게를 삽입하고 q에서 삭제한다.

• 이 모든 과정을 v의 크기가 q와 같을때까지 반복한다. (즉, 모든 트럭이 다리를 건널때 까지)

코드는 다음과 같다.

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

struct INFO
{
    int weight;
    int enter_time;
};

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, check_size = truck_weights.size(), total_weight = 0;
    vector<int> crossed_truck; // 건넌 트럭을 담는 컨테이너
    queue<INFO> q;             // 건너는 트럭을 담는 컨테이너
    
    // 모든 트럭이 다리를 건널때 까지
    while(crossed_truck.size() != check_size)
    {
        // 건너고 있는 트럭이 다리의 끝지점에 도착한 경우
        if(!q.empty() &&  bridge_length <= answer - q.front().enter_time)
        {
           // 현재 다리가 견디는 무게에서 그 트럭 무게를 빼준다.
           total_weight -= q.front().weight;
           // 건넌 트럭이므로 트럭 무게를 컨테이너에 담는다.
           crossed_truck.push_back(q.front().weight);
           // 큐에서 삭제한다.
           q.pop();
        }
        
        // 다리를 건널 트럭이 있고 그 트럭이 건너도 다리가 무게를 견디는 경우
        if(!truck_weights.empty() && weight >= total_weight + truck_weights.front())
        {
            // 현재 다리가 견디는 무게에서 건널 트럭 무게를 더한다.
            total_weight += truck_weights.front();
            // 큐에 트럭 무게와 경과 시간을 삽입한다.
            q.push(INFO{truck_weights.front(), answer});
            // 이제는 대기 트럭이 아니므로 삭제한다. 
            truck_weights.erase(truck_weights.begin());
        }
        // 경과 시간을 갱신한다.
        ++answer;
    }
    return answer;
}