Programmers / Stack, Queue / 다리를 지나는 트럭

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/42583

< 풀이 >

1. (트럭무게, 도착시간)의 쌍을 만들어서 각 트럭을 관리하고, 트럭들이 추가되고 나가고 할 수 있는 queue을 만든다.

2. 먼저, 다리에 있는 트럭 중 나갈 시간이 된 트럭을 큐에서 pop 한다.

3. 대기 중인 트럭 중 다음 들어갈 차례인 트럭이 다리에 올라갈 수 있다면, 추가시키고 현재시간을 1 증가 시킨다.

3-else. 들어갈 수 없다면, 다리에서 가장 먼저 올라간 트럭의 도착시간으로 현재시간을 이동시킨다.

-> 이 경우를 설정해주지 않으면 시간은 1씩 계속 증가해야하므로 시간초과가 예상된다.

< 코드 >

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

typedef struct NODE {
    int t_weight;		// 트럭 무게
    int arr_time;	// 도착 시간
}node;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 1;	// 현재 시간
    int cur_weight = 0;	// 현재 다리에 실린 무게
    int next_idx = 0;	// 다음 다리에 올라갈 트럭 번호
    int t_num = truck_weights.size();	// 트럭 수
    queue<node> bridge;

    while (next_idx < t_num || !bridge.empty()) {
        // 1. 현재 나갈 차례인 차가 있는 경우
        if (!bridge.empty() && time == bridge.front().arr_time) {
            cur_weight -= bridge.front().t_weight;
            bridge.pop();
        }
        // 2. 다음 넣을 차량이 있는 경우
        if (next_idx != t_num) {
            // 2-1. 현재 다리에 다음 차량을 넣을 수 있다면...
            if ((weight - cur_weight) >= truck_weights[next_idx]) {
                cur_weight += truck_weights[next_idx];
                bridge.push({ truck_weights[next_idx], time + bridge_length });
                next_idx++;
                time++;
            }
            // 2-1-else. 넣을 수 없다면 시간만 이동
            else {
                time = bridge.front().arr_time;
            }
        }
        // 2-else. 다 넣은 경우 다리에 남은 차가 있다면 남은 시간 처리
        else {
            if(!bridge.empty()) time = bridge.front().arr_time;
        }
    }
    return time;
}

int main(void)
{
    int bridge_length = 2;
    int weight = 10;
    vector<int> truck_weights = { 7, 4, 5, 6 };

    cout << solution(bridge_length, weight, truck_weights) << endl;
}