(자바스크립트 알고리즘) 다리를 지나는 트럭 - kimyang-sun

자바스크립트 알고리즘 (Programmers)

---

문제 설명

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

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

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

제한 조건

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

입출력 예

---

문제 풀이

function solution(bridge_length, weight, truck_weights) {
  let trucks = truck_weights.map(truck => ({
    weight: truck,
    time : 0,
  }));
  let crossing = [];
  let arrivedTrucks = [];
  let currentWeight = 0;
  let time = 0;
  
  // 다리를 지나는 함수
  function cross(trucks) {
    if (trucks[0]) {
      if (currentWeight + trucks[0].weight <= weight) {
        let truck = trucks.shift();
        truck.time++;
        crossing.push(truck);
        currentWeight += truck.weight;
      }
    }
  }
  
  // 트럭이 전부 도착하면 멈추는 반복문
  while (truck_weights.length !== arrivedTrucks.length) {
    crossing.forEach(truck => {
      if (truck.time >= bridge_length) {
        arrivedTrucks.push(crossing.shift());
        currentWeight -= truck.weight;
      }
    });
    crossing = crossing.map(truck => ({
      weight: truck.weight,
      time : truck.time + 1,
    }))
    cross(trucks);
    time++;
  }
  return time;
}

풀이입니다.

 

풀면서 막막했지만 하나하나씩 생각해가며 코드를 작성하니까 완성할 수 있었습니다 😥

 

우선 trucks 라는 객체 배열을 만들어줍니다. 트럭의 무게를 넣어주고 시간은 0 으로 넣어줍니다.

 

crossing 배열은 현재 다리를 지나고 있는 트럭들의 배열이고

arrivedTrucks 배열은 도착한 트럭들의 배열입니다.

currentWeight 는 현재 다리위에 있는 트럭들의 총 무게값이고 처음엔 0 으로 할당합니다.

time은 총 걸린 시간으로 처음엔 0초 입니다.

 

cross 함수를 만들어주는데 만약 trucks에 하나라도 객체가 존재한다면

currentWeigth와 들어가야하는 trucks[0]의 무게를 더한값이 weight와 같거나 작으면

새로운 트럭이 진입해도 되는 상황이기 때문에 crossing에 새로운 트럭을 push 해줍니다.

푸시 해줄때 들어가는 트럭의 time은 1이 됩니다.

그리고 currentWeigth에 들어간 truck의 무게를 더해주는 함수입니다.

 

이제 트럭이 전부 도착하면 멈추게 되는 while 반복문을 돌려줍니다.

crossing에 지나가고 있는 트럭이 하나라도 존재하면 forEach를 통해 각각 트럭의 시간과 다리길이를 비교하여

도달하는 순간 arrivedTrucks에 crossing에 트럭을 push 해줍니다.

당연히 지나간 트럭의 무게는 currentWeight에서 빼줍니다.

 

그 후에는 crossing을 새롭게 할당해주는데 트럭의 무게는 그대로 두고 time을 1씩 증가시킵니다.

 

그다음 cross(trucks)를 통해 다시 트럭이 들어갈 수 있으면 넣어줍니다.

 

마지막은 걸린 시간인 time을 1 증가시켜줍니다.

 

반복문이 끝나고나면 총 걸린 시간인 time을 리턴해줍니다.

 

다른 사람들의 풀이

function solution(bridge_length, weight, truck_weights) {
    // answer: 걸린 시간
    let answer = 0;
    
    // queue: 현재 다리상태
    let queue = [];
    
    // queueSum: 현재 다리 무게
    let queueSum = 0;
    
    // queue의 길이는 다리 길이로 하고 다리 하나하나를 0으로 초기화
    for(let i =0;i<bridge_length;i++){
        queue.push(0);
    }
    
    // now_truck : 현재 다리를 지나가는 트럭
    let now_truck = truck_weights.shift();
    
    // 큐에 트럭을 넣고 다리를 앞으로 한칸씩 땡김
    queue.unshift(now_truck);
    queue.pop();
    
    // 다리 무게 증가
    queueSum += now_truck;
    
    // 시간 증가
    answer++;
    
    // 쉬지않고 큐에 트럭을 넣거나 다리를 건너기 때문에 queueSum 이 0이 되면 모든 트럭이 지나간 것.
    while(queueSum){ 
        // 다리에 있는 트럭 이동
        queueSum -= queue.pop();
        
        // 일단 다리를 안건넌 트럭 하나 빼고,
        now_truck = truck_weights.shift();
        
        // 다리에 들어갈 수 있으면 큐(다리)에 트럭 넣고 무게 증가
        if(now_truck+queueSum<=weight){
            queue.unshift(now_truck);
            queueSum+=now_truck;
        }
        // 다리에 들어갈 수 없으면 0을 넣고 뺏던거 다시 트럭집단에 고스란히 넣어줌
        else{
            queue.unshift(0);
            truck_weights.unshift(now_truck);
        }
        answer++;
    }
    return answer;
}