[programmers]ブリッジトラック

問題の説明

何台ものトラックが規定の順序で川の橋を渡りたいと思っています.すべてのトラックが橋を渡るのに少なくとも数秒かかります.トラックは毎秒1移動し、橋の長さはbridge lengthで、足は重量に耐えられる.
※トラックが橋に完全に上がっていない場合は、トラックの重量は考慮しません.
solution関数のパラメータは、ブリッジ長bridge length、足が受ける重量、トラック1台あたりの重量cart weightsである.解の関数を完了し、すべてのトラックが橋を渡るのに少なくとも数秒かかります.

せいげんじょうけん

bridge lengthは1 10000より大きい.

重量は1以上10000以下である.

cart weightsの長さは1または10000以下です.

すべてのトラックの重量は1以上です.

ソースコード

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を押すことです.
そして、最後のトラックに時間を追加!!