[프로그래머스] 다리를 지나는 트럭 (Javascript)

문제링크

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

분류 

 - Stack / Queue

1. 풀이 힌트

 - 다리에 올라간 트럭들을 관리하는 배열을 생성한다. (bridge)

 - 해당 배열에는 무게(w) 및 다리를 건너기 까지 남은 시간(t)을 props로 갖는 객체(truck)를 관리한다.

 - 다리에 올라갈 수 있는 무게의 허용치 (curWeight)와 다리의 길이를 판단하여 bridge에 truck을 추가한다. (addTruckInTheBridge)

 - while문의 매 시행은 시간이 가는 것에 비례하며, 매 시행마다 bridge를 체크하여 시간이 끝난 트럭은 제거하고, 시간 및 무게를 변화시킨다 (filterTrucksInTheBridge)

2. 코드 풀이

// Level2: 다리를 지나는 트럭 (스택/큐)

function solution(bridge_length, weight, truck_weights) {
  let answer = 1;
  let trucksInBridge = [{ w: truck_weights[0], t: bridge_length - 1 }];
  let maximumWeight = weight - truck_weights[0];
  truck_weights.shift();

  const getTrucksInBridge = (preTrucksInBridge) => {
    return preTrucksInBridge
      .reduce((acc, cur) => {
        if (cur.t > 0) {
          return [...acc, cur];
        }
        maximumWeight += cur.w;
        return acc;
      }, [])
      .map((truck) => ({
          ...truck,
          t: truck.t - 1,
      }));
  };

  const addTruckToBridge = (truckWeight) => {
    truck_weights.shift();
    trucksInBridge.push({ w: truckWeight, t: bridge_length - 1 });
    maximumWeight -= truckWeight;
  };

  const checkTruckCanCrossTheBridge = (truckWeight, lengthOfTrucksInBridge) => {
    return maximumWeight - truckWeight >= 0 && lengthOfTrucksInBridge < bridge_length
  } 

  while (trucksInBridge.length) {
    answer++;
    trucksInBridge = getTrucksInBridge(trucksInBridge);
    let curTruckWeight = truck_weights[0];
    if (checkTruckCanCrossTheBridge(curTruckWeight, trucksInBridge.length)) {
      addTruckToBridge(curTruckWeight);
    }
  }

  return answer;
}

3. 다른 사람 풀이

트럭이 나갈 때 까지 기다리는 시간 만큼 실제 반복문을 안 돌아도 되므로 효율 Up

function solution2(bridge_length, weight, truck_weights) {
  let time = 0,
    bridge = [[0, 0]],
    weightOnBridge = 0;

  while (bridge.length > 0 || truck_weights.length > 0) {
    if (bridge[0][1] === time) weightOnBridge -= bridge.shift()[0];

    if (weightOnBridge + truck_weights[0] <= weight) {
      weightOnBridge += truck_weights[0];
      bridge.push([truck_weights.shift(), time + bridge_length]);
    } else {
      if (bridge[0]) time = bridge[0][1] - 1;
    }
    time++;
  }
  return time;
}