다리를_지나는_트럭.md

다리를 지나는 트럭

문제 링크

문제 설명

길이제한과 무게제한이 있는 1차선 다리를 각 무게가 다른 트럭이 건너간다고 할 때 모든 트럭이 다리를 건너 갈 때 걸리는 시간은?

문제 풀이

다리를 queue로 만들고 트럭이 다리에 진입 할 때 queue에 offer() 빠져나올때 poll()해준다.
풀이1: 반복 단위를 초 단위로 체크하면서 푼다. 트럭이 못 올라갈때는 queue에 0을 넣어서 맞춰준다.
풀이2: 진출입 이벤트 기준으로 푼다. 다리에 제한조건에 걸리지 않을 때까지 queue에 자동차 들을 넣고 최대 무게가 차면 현재시간에 상단큐의 진출 시간을 업데이트하고 다음 대기중인 자동차의 진입시간을 현재시간으로 맞춰서 넣는다.

풀이2는 테스트 케이스는 성공하나 풀이는 실패

풀이코드

풀이1

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {

        int time = 0;
        int sum_weight = 0, idx=0;
        Queue<Integer> queue = new LinkedList<>();

        while(true){
            if(idx == truck_weights.length)break;
            if(queue.size() == bridge_length){
                sum_weight-=queue.poll();
            }
            else if(sum_weight+truck_weights[idx]>weight){
                queue.offer(0);
                time++;
            }else{
                queue.offer(truck_weights[idx]);
                sum_weight+=truck_weights[idx];
                time++;
                idx++;
            }
        }
        return time + bridge_length;
    }
}

풀이2. 실패코드

import java.util.Queue;
import java.util.LinkedList;
class Truck {
  int weight;
  int time;
  public Truck (int weight, int time) {
      this.weight = weight;
      this.time = time;
  }
}
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {

        int nowTime = 0;
        int nowTruckWeight = 0, idx=0;
        Queue<Truck> queue = new LinkedList<>();


        while(true){
            //마지막 트럭이 다리에 올라갔을 때, 벗어난다.
            if(idx == truck_weights.length){
                while(!queue.isEmpty()){
                    Truck truck = queue.poll();
                    nowTime = truck.time + bridge_length;
                }
                break;
            }
            if(nowTruckWeight+truck_weights[idx]>weight || queue.size() == bridge_length){ //다음 들어 올 트럭 무게 초과되거나 다리 가득 찼으면  기존꺼 빼준다.
                Truck truck = queue.poll();
                nowTruckWeight-=truck.weight;
                nowTime = truck.time + bridge_length;
            }else{
                if(!queue.isEmpty())nowTime++;
                queue.offer(new Truck(truck_weights[idx],nowTime));
                nowTruckWeight +=truck_weights[idx];
                idx++;
            }
        }

        // 9. 마지막 트럭이 다리에 올라간 상태에서 다리의 길이를 더해주면, 모든 트럭이 통과하는데 걸린 시간.
        return nowTime+1;
    }
}