プログラマー-ブリッジトラック


1.質問


質問リンク


2.解答


2-1. 条件

  • ブリッジは重量以下の重量に耐えられる.
  • 2-2. に答える


    Qを利用して問題を解く
    行列で表すものには「橋」(a)と「順番に待つトラック」(b)がある.
  • b最前面のトラック重量と「ブリッジトラックの総重量」(sum of weight)の和
    足が耐えられる重さ以下なら
    bの先頭のトラックを取り出し、「[トラック重量、時間](c)に加工してaに入れる.
    sum of weightsをcの重量に増やします.

  • 各ループは、ブリッジ(a)上のトラックの時間と正確な答え「時間」(ans)を増加させる.

  • 時間が過ぎた.
    aの一番前の要素cの時間がブリッジの長さより大きい場合、
    aからcを削除し、sum of weightsからcの重量を減算します.

  • 上記の手順を繰り返し、aおよびbにトラックがなくなると、ループから逃げる.
  • 3.完全なコード

    function solution(bridge_length, weight, truck_weights) {
        const bridge = [];
        let ans = 0;
        let weight_of_trucks_on_bridge = 0;
        
        // 4. 1, 2, 3을 반복하다가 a와 b에 더 이상 트럭이 남아있지 않다면 루프를 탈출합니다.
        while (truck_weights.length || bridge.length) {
            // 2. 매 루프마다 다리(a)위의 트럭들의 시간들과 정답인 '시간'(ans)을 증가시킵니다.
            bridge.forEach(truck => truck[1]++);
            ans++;
            
           /**
            * 3.
            *   시간이 지나서
            *   a의 맨 앞의 요소 c의 시간이 다리의 길이보다 크다면
            *   a에서 c를 제거하고 sum_of_weight에서 c의 무게 만큼 감소시킵니다.
            */
            if (bridge.length && bridge[0][1] > bridge_length) {
                let truck = bridge.shift();
                weight_of_trucks_on_bridge -= truck[0];
            }
    
            /**
             * 1.
             *  b의 맨 앞에 있는 트럭의 무게와 '다리 위의 총 트럭들의 무게'(sum_of_weight)의 합이
             *  다리가 버틸 수 있는 무게보다 작거나 같다면 
             *  b의 맨 앞의 트럭을 빼와서 **'[트럭 무게, 시간]'(c)**으로 가공해서 **a**에 넣고
             *  sum_of_weight**를 **c**의 무게만큼 증가시킵니다.
             */
            const truck_weight = truck_weights[0];
             
            if (weight_of_trucks_on_bridge + truck_weight <= weight) {
                weight_of_trucks_on_bridge += truck_weight;
                bridge.push([truck_weight, 1]);
                truck_weights.shift();
            }
        }
    
        return ans;
    }
    橋に何台のトラックがあるか検査する必要はありません.
    どうせ橋の上でトラックが溢れ出す前に
    トラックを走らせてこそ、最小限の時間を稼ぐことができるからだ.