[Programmers] 다리를 지나는 트럭

문제 설명

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

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

제한 사항

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

소스코드

C++

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int sum = 0, idx = 0;
    queue<int> q;
    
    while(1) {
        answer++;
        // 큐의 길이와 다리의 길이가 같으면 트럭이 도착한 것
        if(q.size() == bridge_length) {
            sum -= q.front();
            q.pop();
        }

        // 다음 트럭이 다리를 지나갈 수 있으면
        // 다음 트럭의 무게를 더한 합이 다리의 무게보다 작으면, 트럭 push
        if(sum + truck_weights[idx] <= weight) {
            // 마지막 트럭이면 마지막 트럭의 길이만큼 시간을 더해준다.
            if(idx == truck_weights.size()-1) {
                answer += bridge_length;
                break;
            }
            q.push(truck_weights[idx]);
            sum += truck_weights[idx];
            idx++;
        }
        // 다음 트럭의 무게를 더한 합이 다리의 무게보다 크면 0을 push해
        // 트럭의 도착 시간을 맞춰준다.
        else {
            q.push(0);
        }
    }
    
    return answer;
}

Java

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int sum = 0, i = 0;
        Queue<Integer> q = new LinkedList<>();
        for(int truck : truck_weights) {
            while(true) { // 트럭 올릴 때 까지 반복
                answer += 1;
                // 큐가 비어있으면 다리에 트럭 올림.
                if(q.isEmpty()) {
                    q.add(truck);
                    sum += truck;
                    break;
                }
                // 다리에 트럭이 최대로 올라가면 큐에서 제거
                if(q.size() == bridge_length) {
                    sum -= q.poll();
                }
                // 다리에 트럭 더 올릴 수 있으면 큐에 추가
                if(sum + truck <= weight) {
                    q.add(truck);
                    sum += truck;
                    break;
                }
                // 못 올리면 0 추가
                else {
                    q.add(0);
                }
            }
        }
        
        return answer + bridge_length;
    }
}

소감

0을 push해주는게 포인트였다,,
그리고 마지막 트럭이 건너는 시간을 추가해줘야한다!!