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

문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2대까지, 무게 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한사항

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

풀이

while 루프를 한 번 돌 때마다 time값이 1씩 커진다. startTimes 큐 안에는 현재 다리 위를 지나고 있는 트럭들이 다리에 진입한 시점을 저장한다.

이 때 다리 위의 트럭 중 맨 앞에 있는 트럭, 즉 startTime.front()의 트럭이 모두 지난 시간이라면 해당 트럭을 큐에서 pop하고 다리 위 트럭의 무게도 빼준다. trucks vector에서도 제거해서 해당 트럭이 다리를 다 건넜음을 표시한다.

만약 다음으로 다리를 건널 차례인 트럭의 weight과 현재 다리 위 트럭들의 weight들의 합이 maxWeight 이내이고, 새 트럭이 들어갈 자리가 있으면 현재 time을 startTimes 큐에 push해서 새 트럭이 다리에 진입한 것을 표시한다.

마지막 트럭이 다리에 진입하면 while loop에서 벗어나게 되고, 이 때의 time값에 다리의 length를 더한 값이 모든 트럭이 다리를 건넌 시간이므로 (time + length)를 return한다.

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

int solution(int length, int maxWeight, vector<int> trucks) {
    int time = 0;
    int weight = 0;
    int index = 0;
    queue<int> startTimes;
    
    while (trucks.size() != index) {
        time++;
        if (!startTimes.empty()) {
            if (time - startTimes.front() == length) {
                startTimes.pop();
                weight -= trucks[0];
                trucks.erase(trucks.begin());
                index--;
            }
        }
            
        if (weight + trucks[index] <= maxWeight && startTimes.size() < length) {
            weight += trucks[index];
            startTimes.push(time);
            index++;
        }
    }
    
    return time + length;
}

출처: https://programmers.co.kr