[프로그래머스] 다리를 지나는 트럭 (Lv 2) - javascript

📝 문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 이하입니다.
     

🔑풀이

풀이 유형은 두 가지가 있다.
bridge_length 크기의 배열을 0으로 채워 트럭 무게를 값으로 추가해가며 다리를 추상화하는 과정을 같다.
하지만 트럭이 모두 올라간 뒤에 계속해서 빈 자리를 0으로 채우느냐, 아니면 하나씩 제거하느냐에 따라 코드가 달라진다.
 

1. 계속해서 빈 자리를 채우는 풀이

function solution(bridge_length, weight, trucks) {
    
    let finish = [];
    let ing = new Array(bridge_length).fill(0);
    let sec = 0;
    let truckCnt = trucks.length;
    let weightSum = 0;

    while(finish.length !== truckCnt) {
        
        let outTruck = ing.shift();
        
        if(outTruck) {
            finish.push(outTruck);
            weightSum -= outTruck; 
        }
        
        if(weightSum + trucks[0] <= weight) {
            let inTruck = trucks.shift();
            ing.push(inTruck);
            weightSum += inTruck;
        }
        else ing.push(0);
        
        sec++;
    }
    
    return sec;
}

 

• 풀이 주석

function solution(bridge_length, weight, trucks) {
    
    let finish = []; // 다리를 건넌 트럭들
    let ing = new Array(bridge_length).fill(0); // 건너고 있는 트럭들
    let truckCnt = trucks.length; // 트럭 개수
    let sec = 0; // 건너는 시간
    let weightSum = 0; // 다리 위 무게

    while(finish.length !== truckCnt) { // 트럭이 모두 건너가면 stop
        
        let outTruck = ing.shift(); // 다리 맨 앞 값 빠져나감
        
        if(outTruck) { // 뺀 값이 0이 아니면 (트럭이면)
            finish.push(outTruck); // 건넌 트럭에 합류
            weightSum -= outTruck; // 다리 위 트럭 무게에서 뺌
        }
        
        if(weightSum + trucks[0] <= weight) { // 다음 트럭 넣어도 무게 넘지 않으면
            let inTruck = trucks.shift(); // 다음 트럭
            ing.push(inTruck); // 트럭 맨 뒤에 추가
            weightSum += inTruck; // 무게에 넣기
        }
        else ing.push(0); // 만약 무게 넘으면, 맨 뒤에 0 넣음
        
        sec++; // 위 과정을 할 때마다 1초씩 증가
    }
    
    return sec;
}

 

다리 형태의 배열을 만들어서 하나씩 앞으로 밀고, 뒤에 추가해가며 초를 세는 방법

 

• 정확도 테스트 결과

 

2. 대기 트럭이 없을 시, 다리 위 요소를 하나씩 제거하는 풀이

function solution(bridge_length, weight, truck_weights) {
  let bridge = new Array(bridge_length).fill(0)
  let sec = 0;

  while (bridge.length) {

    bridge.shift(); 
    sec += 1;

    if (truck_weights.length) { // 대기 트럭 존재하면

      let totalWeight = bridge.reduce((sum, v) => sum + v, 0);

      if (totalWeight + truck_weights[0] <= weight) {
        bridge.push(truck_weights.shift());
      } else {
        bridge.push(0);
      }
    }
  }
  return sec;
}

 
대기 트럭 존재 유무를 조건으로 검사해서 없다면, 굳이 값을 추가하지 않는다.
훨씬 코드가 깔끔하지만 속도가 엄청나게 느려진다.
 

• 정확도 테스트 결과

 

---

참고

https://velog.io/@kimtaeeeny/

https://kyoung-jnn.tistory.com/entry/