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

 

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

 

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

프로그래머스

---

 

 

해결방안

 

큐 Queue

---

 

 

코드

 

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

int solution(int bl, int w, vector<int> tw) {

    queue<pair<int, int>> Q; // tw의 진입시간, 무게
    Q.push({ 0, tw[0] }); // 첫 번째 트럭이 다리에 진입: 진입시간 0, 무게는 tw[0]
    int i = 1;
    int totalWeight = tw[0];
    int answer = 1; // answer: 현재시간

    while (true)
    {
        // 다리 위에 트럭이 있고, 가장 먼저 진입한 트럭이 다리를 건너는 데 필요한 시간이 지났다면, 이 트럭은 다리를 빠져나간다. 이 트럭의 무게는 totalWeight에서 빼고, 큐에서 제거.
        if (!Q.empty() && answer - Q.front().first == bl) // 현재시간 - i번째 트럭이 진입한 시간 == 다리의 길이
        {
            totalWeight -= Q.front().second;
            Q.pop();
        }

        // 아직 다리를 건너지 않은 트럭이 있고, 그 트럭을 포함한 모든 트럭의 무게가 다리의 최대하중을 초과하지 않는다면, 이 트럭은 다리에 진입한다.
        // 이 트럭의 진입 시간과 무게가 큐에 추가되고, 무게는 totalWeight에 더해진다.
        if (i < tw.size() && totalWeight + tw[i] <= w)
        {
            Q.push({ answer, tw[i] }); // 트럭이 다리로 진입하는 시간을 저장
            totalWeight += tw[i];
            i++;
        }

        answer++; // 시간 1초씩 증가

        if (Q.empty() && i == tw.size()) break; // 모든 트럭이 다리를 건너고, 더 이상 처리할 트럭이 없을 때
    }

    return answer;
}

int main()
{
    vector<int> testcase1 = { 7,4,5,6 };
    vector<int> testcase2 = { 10 };
    vector<int> testcase3 = { 10,10,10,10,10,10,10,10,10,10 };

    cout << solution(2, 10, testcase1) << "\n";
    cout << solution(100, 100, testcase2) << "\n";
    cout << solution(100, 100, testcase3) << "\n";

    return 0;
}

 

 

---