프로그래머스 JS | 다리를 지나는 트럭

❌ Solution ( 14.3 / 100 )

function solution(bridge_length, weight, truck_weights) {
    const totalTrucks = truck_weights.length;
    let timer = 0;
    let load = 0;
    const onBridge = [];
    const complete = [];
    
    while(totalTrucks !== complete.length) {
        if( load + truck_weights[0] <= weight) {
            // 현재 load 값과 다음 트럭의 무게의 합이 weight 보다 작으면, onBridge 다음 트럭을 넣고 timer를 추가한다. 
            // load 에는 다리 위에 올라간 트럭의 무게를 더한다. 그리고 onBridge 배열에 트럭을 추가한다.
            // onBridge 트럭에 추가된 트럭은 truck_weights 배열에서 제거 
            onBridge.unshift(truck_weights[0]);
            load += truck_weights[0];
            truck_weights.shift();
            timer++;
        } else {
            // load 값이 더 크다면, onBridge에 빈 트럭을 넣고, timer를 추가한다. 
            onBridge.unshift(0);
            timer++;
        }
        
        // 만약 onBridge의 length 가 bridge_length 값보다 크다면 onBridge 배열의 마지막 값을 배열에서 제거한다. 
        // 이때 제거되는 값이 0이 아니면 load 값에서도 해당 값을 빼준다. 
        // 트럭이 완전히 다리를 넘어가면 complete 배열에 추가한다. complete 배열과 totalTrucks 값이 같다면 timer 를 return 한다.
        if( onBridge.length > bridge_length) {
            const del = onBridge[onBridge.length-1];
            if (del !== 0) load = load - del;
            complete.push(del);
            onBridge.pop();
        } 
        console.log(timer, load, complete, onBridge, truck_weights);
    } 
    
    return timer;
}

하지만 위 로직은 2개의 테스트 케이스는 통과했지만 테스트 케이스 1번은 통과하지 못했다.

콘솔에 확인을 해본 결과, 트럭이 다리를 건너며 load가 업데이트 되고, 업데이트된 load 값에 따라 새로운 트럭이 들어오는 과정이 한번에 처리되지 않고 분할 처리되어 발생하는 문제로 파악되었다. 

onBrigde 배열의 길이가 다리의 길이보다 길어졌을 때 onBridge 배열의 마지막 인자를 처리하고 업데이트 되는 load 값에 따라 다음 단계에서 처리될 코드들을 내부에 함께 넣어서 위 사진에서 3~4 번째 실행될 코드가 한번에 처리될 수 있도록 코드를 추가하였다. 

...
	if( onBridge.length > bridge_length) {
            const del = onBridge[onBridge.length-1];
            if (del !== 0) {
                load = load - del;
                complete.push(del);
            }
            if (load + truck_weights[0] <= weight) {
                onBridge.unshift(truck_weights[0]);
                onBridge.pop();
                load += truck_weights[0];
                truck_weights.shift();
            }
        }
...

하지만 이렇게 코드를 작성할 경우 시간초과로 역시 오답이 출력되었다. 

shift, unshift 메소드의 시간복잡도가 커서 발생하는 문제로 추측된다.

✅ Solution(100 / 100)

const bridge_length = 2;
const weight = 10;
const truck_weights = [7,4,5,6];

function solution(bridge_length, weight, truck_weights) {
  const trucks = [...truck_weights];
  
  const passed = []; // 지나간 트럭 배열.
  const bridge = []; // 다리
  let bridgeWeight = 0; // 지금 다리의 무게
  let count = 0; // 지나간 초, return 할 값.
  
  // 파라미터로 들어온 truck_weights의 길이와 지나간 트럭 배열의 길이가 다를 동안.
  while(passed.length !== truck_weights.length){
    count++;
    // 만약 다리 배열 bridge의 마지막이 숫자라면
    if(typeof bridge[bridge_length-1] === 'number'){
      const truck = bridge.pop(); // 마지막 트럭을 다리에서 빼낸다.
      bridgeWeight -= truck; // 트럭의 무게만큼 지금 무게에 뺀다.
      // 트럭이 0보다 크면 (실제 트럭) 지나간 트럭 배열에 넣는다.
      if(truck > 0) passed.push(truck); 
    }
    
    //지금 무게와 1번 트럭이 통과 가능하면
    if(trucks[0] + bridgeWeight <= weight){
      bridgeWeight += trucks[0]; // 트럭을 다리에 넣음.
      bridge.unshift(trucks.shift()); // 다리에서 앞으로 넣어준다.
    }else{
      // 트럭이 못지나가므로 빈트럭 0 을 넣어 준다.
      bridge.unshift(0);
    }
  }
  return count;
}

혼자서는 해결책을 찾지 못해 다른사람들의 여러 풀이를 찾아보았는데, 이 풀이가 가장 직관적이고 간단한 것 같다.

출처
- ScriptKid, velog, [코딩테스트/JS] 다리를 지나는 트럭