Dony :)

FE로 성장 중 🌱

문제 설명

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

답안

나의 풀이

function solution(bridge_length, weight, truck_weights) {
  let time = 0;
  const bridge = [];
  let bridge_weight = 0;
  while (truck_weights.length) {
    time++;
    if (bridge.length >= bridge_length) {
      bridge_weight -= bridge.shift();
    }
    if (bridge_weight + truck_weights[0] <= weight) {
      bridge.push(truck_weights[0]);
      bridge_weight += truck_weights.shift();
    } else {
      bridge.push(0);
    }
  }
  return time + bridge_length;
}

시간복잡도: O(N2)

  1. 모든 트럭이 다리를 건널 때 걸리는 시간인 time, 다리를 건너가고 있는 트럭들을 담을 배열 bridge와 다리 위의 트럭들의 무게를 저장할 bridge_weight를 생성한다.
  2. 다리 위에 오를 때마다 truck_weights에서 pop해주어야 하므로 truck_weigths.length가 0이 될 때까지 while문을 돈다.
  3. 트럭이 건널 때마다 반복문을 돌므로 time++해준다.
  4. 다리 위의 트럭의 개수가 bridge_length 이상이 되면 다리에서 먼저올라 간 트럭이 내려와야하므로 bridge.shift를 하여 다리 위의 트럭 무게인 bridge_weight에서 빼준다.
  5. 다리 위의 트럭 무게(bridge_weight)와 첫번 째 대기 트럭(truck_weights[0])의 합이 제한 무게(weight) 이하면, 다리를 건너 갈 수 있으므로 bridge에 첫번 째 대기 트럭(truck_weights[0])을 push한다.
    그리고 다리 위의 트럭 무게(bridge_weight)에 첫번 째 대기 트럭(truck_weights[0])의 무게를 shift하여 더한다.
  6. 다리 위의 트럭 무게(bridge_weight)와 첫번 째 대기 트럭(truck_weights[0])의 합이 제한 무게(weight) 초과면, 다리를 건널 수 없으므로 0을 push한다. (위에서 bridge.length를 체크해야하므로 건너는 트럭이 없더라도 push를 해야한다. 그러나 무게에 영향을 주지 않기 위해 0을 push한다.)
  7. while문이 순회가 끝날 때 마지막 대기 트럭이 다리에 막 올라갔을 때이므로 마지막 트럭이 다리를 건너는 시간인 bidge_length를 time에 더해 반환해준다.

참고