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

문제

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

입출력 예시

첫 풀이

요약

트럭은 정해진 순서대로 다리를 건넌다.
다리를 건너는 트럭 무게의 총합은 다리가 견딜 수 있는 무게를 넘을 수 없다.
모든 트럭이 완전히 다리를 건너야 한다.
트럭은 1초에 1씩 다리 위를 움직인다.

 

첫 풀이 방법

우선 다리를 건너고 있는 트럭 무게를 위한 Queue 자료구조를 선언한다.
그리고 다리를 건너고 있는 트럭의 시간을 위한 큐를 선언한다.
자바스크립트에는 별도의 Queue 자료형이 없으므로, 배열을 선언하고 shift, push 메소드를 사용 할 것.

대기중인 트럭이 다리를 건널 수 있는지, 각 초마다 다리에 있는 트럭의 총 무게를 조사한다.
모든 트럭은 1초에 1만큼만 움직이므로, 각 트럭마다 건너는 시간은 다리의 길이와 같다. 그러므로 별도로 선언한 시간 큐를 이용한다.
큐의 맨 처음 시간이 가장 먼저 다리를 지나는 트럭의 시간이므로 그 시간이 다리의 길이와 같을 때 큐에서 트럭을 빼준다.
다리 건너기를 대기하고 있는 트럭이 없고, 큐에 트럭이 존재하지 않을 때 반복문이 종료된다.

function solution(bridge_length, weight, truck_weights) {
  const truckQueue = []; // 각 트럭 무게를 위한 큐
  let timeQueue = []; // 각 트럭이 다리를 건너는 시간을 위한 큐
  let totalTime = 0; // 총 건너는 시간
  let weightSum = 0; // 다리를 건너는 중인 트럭 무게들의 합

  while (true) {
    if (weightSum + truck_weights[0] <= weight) {
      const tWeight = truck_weights.shift();
      truckQueue.push(tWeight);
      weightSum += tWeight;
      timeQueue.push(0);
    } 
    // 다리에 있는 트럭 무게 합 + 대기중인 트럭 무게 <= 다리가 견디는 트럭 무게라면
    // 대기중인 트럭 무게를 tWeight에 넣어주고, 무게 큐에 넣고, 
    // 다리를 건너는 트럭 무게 합을 늘려주고 시간 큐에 0을 넣어준다.

    timeQueue = timeQueue.map((time) => time + 1);
    totalTime++;
    // 1초에 1씩 이동하므로 각 시간을 1씩 늘려주고, 총 건너는 시간을 1 늘린다.    

    if (timeQueue[0] === bridge_length) {
      weightSum -= truckQueue.shift();
      timeQueue.shift();
      // 다리 가장 앞에 있는 트럭의 이동시간이 다리의 길이와 같으면 다리의 끝에 위치하므로
      // (아직 다리를 완전히 다 건넌 것이 아니다.) 각 큐에서 첫번째 값을 빼준다.
      if (truck_weights.length === 0 && timeQueue.length === 0) break;
      // 만약 대기중인 트럭이 없고, 다리를 지나는 중인 트럭도 없다면 while문을 탈출한다.
    }
  }
  return totalTime + 1;
  // while을 break로 탈출할 때 사실 트럭이 다리 끝에 위치한 시점에 탈출한 것이므로, 
  // 1초를 더해줘야 완전히 다리를 지난 시간이다.
}

코드 정리해보기

다음과 같이 코드를 짜면 정답은 잘 나온다.
무작정 코드를 쓰다 보니 불필요한 코드가 많아진 것 같아서, 내가 짠 코드를 가지고 조금 정리해 보겠다.

1. 큐를 두개 씩이나 쓸 필요는 없어보인다. 큐를 하나만 선언하고 큐에 트럭을 push할 때, [weight, time] 배열을 넣자.
   사실 이것 하나만으로 코드가 꽤나 간단해 질 것 같아서 기대된다.
2. while 조건문에 true 대신 구체적인 탈출조건을 명시해보자.

function solution(bridge_length, weight, truck_weights) {
  let queue = []; // 하나의 큐 선언
  let totalTime = 0; // 총 건너는 시간
  let weightSum = 0; // 다리를 건너는 중인 트럭 무게 합

  while (truck_weights.length !== 0 || queue.length !== 0) { 
      // 이렇게 선언하면 둘 다 0이어야 while문을 탈출한다.
    if (weightSum + truck_weights[0] <= weight) {
      const tWeight = truck_weights.shift();
      queue.push([tWeight, 0]);
      weightSum += tWeight;
    } 
    // 대기중인 트럭이 다리를 건널 수 있으면 [weight, time] 형태로 큐에 넣고, 
    // 다리를 건너는 트럭 무게 합을 증가시킴
    queue = queue.map(([w, t]) => [w, t + 1]);
    totalTime++;
    // 각 트럭들의 시간과 총 소요 시간을 1회 반복당 1씩 늘린다.
    if (queue[0][1] === bridge_length) {
      weightSum -= queue.shift()[0];
    } // 맨 앞 트럭의 시간이 길이와 같으면 트럭이 다리 끝에 위치했으므로(아직 건너지 않았다)
      // 큐에서 빼주고, 다리를 건너는 트럭 무게 무게를 줄여준다.
      // (우선 빼줘야 다음 반복 때 대기 중인 트럭의 출발 여부를 판단한다.)
  }
  return totalTime + 1; 
      // 마지막으로 다리를 건너는 트럭이 다리 끝에 위치할 때 while문이 종료되므로
      // 1초 후에 완전히 트럭이 다리를 건넌다. 
}

이해를 돕기 위한 주석을 추가해둬서 좀 지저분하지만, 그래도 전보다는 더 이해하기 쉬운 코드가 된 것 같다.
단순 제 지식으로만 해결했을 뿐 더 효율적인 코드가 존재할 수 있습니다.