ブリッジトラック

🔗 質問リンク

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

問題の説明

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

⚠▼制限

bridge lengthは1または10000未満です.

Weightは1以上10000以下です.

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

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

💡 プール(言語:JavaとPython)

キューで問題を解く方法は思いついたが、トラックごとに時間を計る方法は思いつかなかった.人の解答を参考にした.各ケースは条件文で区分されます.車1台あたりの時間秒を計算するのではなく、時間全体を単独で計算します.新車がQに入った時、時間+1、Qがいっぱいになったら前の車を走らせます.これ以上の重さがなければ、ゼロ人のトラックにあげて、時間だけを過ぎさせます.

Java

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0, current_weight = 0;
        Queue<Integer> bridge = new LinkedList<>();
        for (int truck : truck_weights) {
            while (true) {
                // 다리에 트럭이 한대도 없으면 넣어주고 시간 +1, 무게 갱신
                if (bridge.isEmpty()) {
                    bridge.offer(truck);
                    answer++;
                    current_weight += truck;
                    break;
                // 다리가 꽉 찼으면 앞의 트럭을 빼주고, 무게 갱신
                } else if (bridge.size() == bridge_length) {
                    current_weight -= bridge.poll();
                // 다리에 다음 트럭이 들어올 여유가 있으면 추가하고, 시간 +1, 무게 갱신
                } else if (current_weight + truck <= weight) {
                    bridge.offer(truck);
                    answer++;
                    current_weight += truck;
                    break;
                // 다리에 무게 여유가 없으면 트럭이 안들어오고(무게 0), 시간 +1
                } else {
                    bridge.offer(0);
                    answer++;
                }
            }
        }
        return answer + bridge_length; // 마지막 트럭이 다리에 올라간 순간 for문 종료, 다 빠져나오는데 걸리는 시간(길이)
    }
}

Python

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    # 다리 위에 존재하는 트럭의 무게와 거리 정보
    on_bridge = [deque([]), deque([])] # 무게, 거리
    # truck_weights를 deque로 바꿔서 사용
    before_bridge = deque(truck_weights)

    # 대기트럭이 존재하지 않고 다리 위에도 트럭이 없을 때까지 반복
    while len(before_bridge) != 0 or len(on_bridge[0]) != 0:

        # 경과시간 1초씩 증가
        answer += 1

        # 맨 처음에 on_bridge[1][0]가 없어서 answer != 1해서 에러 안뜨게
        # 다리 위의 맨 앞의 트럭의 거리가 다리 길이와 같으면 그 트럭은 지금은 지난 트럭
        # 동시에 여러 트럭이 다리를 지날 일은 없어서 맨 앞에 트럭만 검사
        if answer != 1 and on_bridge[1][0] == bridge_length:
            on_bridge[0].popleft()
            on_bridge[1].popleft()

        # 무게가 여유있어 다리에 트럭을 추가하는 경우
        # 대기 트럭이 존재하고 다리 위 트럭들 무게 합 + 대기 트럭 무게 합이 
        # 다리 무게 제한보다 작을 때만 추가
        if len(before_bridge) != 0 and sum(on_bridge[0]) + before_bridge[0] <= weight:
            # 무게, 거리 = 0 입력
            on_bridge[0].append(before_bridge.popleft())
            on_bridge[1].append(0)

        # 매 턴마다 모든 트럭 거리 1씩 증가
        # 트럭들 거리 정보 리스트에 모든 원소 1씩 더해서 다시 저장
        on_bridge[1] = deque(map(lambda x: x+1, on_bridge[1]))

    return answer