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

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

프로그래머스

접근 방법

큐를 이용하여 현재 다리의 무게와 시간을 고려하여 푸는 문제이다. 

• 다리의 무게보다 적다면 트럭이 이동할 수 있다.
• 트럭은 다리의 길이만큼 이동하며 이때 이동 거리는 경과한 시간이다. 

이 두가지만 생각하고 문제를 한단계씩 풀면 비교적 쉽게 풀 수 있다.

풀이

function solution(bridge_length, weight, truck_weights) {
  const bridge = [];
  const time_arr = [];
  let bridge_weight = 0;
  let time = 0;

  while (truck_weights.length > 0 || bridge.length > 0) {
    for (let i = 0; i < time_arr.length; i++) {
      time_arr[i]--;
    }
    if (time_arr[0] === 0) {
      time_arr.shift();
      let truck = bridge.shift();
      bridge_weight -= truck;
    }

    if (bridge_weight + truck_weights[0] <= weight) {
      let truck = truck_weights.shift();
      bridge.push(truck);
      time_arr.push(bridge_length);
      bridge_weight += truck;
    }

    time++;
  }
  return time;
}

무게를 확인하기 위한 배열과 트럭의 시간을 관리하는 배열을 생성하여 각각의 배열을 하나씩 탐색하는 방법으로 해결하였다. 

먼저 다리를 건너는 트럭의 시간을 모두 1씩 감소시켜주었다. 

그후 큐의 특징을 이용하여 무조건 첫번째에 접근하여 첫번째 시간의 값이 0이라면 다리를 건너는 트럭과 시간 배열에서 제거해준 후 현재 다리의 무게에서 트럭의 무게를 빼주었다. 

 

이후 현재 다리의 무게 + 들어올 트럭의 무게가 다리의 제한된 무게보다 적다면 해당 트럭의 무게와 시간을 각각의 배열에 추가해주었다. 

리팩토링

해당 코드의 단점은 2번째 테스트케이스에서 매우 비효츌적이다. 

그 이유는 위의 코드는 시간을 1씩 증가하는데 들어올 차량이 있다면 이렇게 진행해도 괜찮지만 들어올 수 있는 차량이 없다면 굳이 시간이 100초가 되기 위해 100번을 실행하는 것은 비효율적이다. 

들어올 트럭 : []

다리: [10]

다리의 길이: 100

시간: 1 -> 2,3,4,5,6 ... 100번 실행

 

나는 시간을 점프할 생각을 하지는 못했지만 다른 코드를 보고 해당 방법을 알게되었다. 

function solution(bridge_length, weight, truck_weights) {
  const bridge = [[0, 0]];
  
  let bridge_weight = 0;
  let time = 0;

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

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

해당코드는 내가 두개의 배열로 생성한 것을 이차원 배열로 해결하였다. 

또한 시간을 점프하기 위한 코드를 작성함으로 써 불필요한 반복을 제거하였다. 

이때 1을 감소하지 않는다면 반복문 한번에 시간이 2가 증가되기 때문에 해당 코드에서 1을 감소시켜줌으로 써 시간이 2씩 증가하는 것을 방지해줘야 한다.