다리를 지나는 트럭

내 풀이법

문제해석

• 트럭들이 다리를 지나가는데 걸리는 시간을 구하라
• 트럭들은 1초마다 다리의 길이의 1씩 지나간다
• 다리에는 무게제한이 있다 (weight)

 

내가 생각한 풀이법

• 특별한 이벤트 발생할 때와 지속적으로 발생하는 이벤트를 나눠서 코드를 작성함
• 특별한 이벤트의 경우
  • 새로운 트럭이 다리에 진입할 때
  • 다리위의 트럭이 다리의 끝에 도달할 때

• 지속적 이벤트의 경우
  • 한 턴마다 시간이 1씩 증가함
  • 트럭이 1초마다 다리를 1씩 지나감

나의 코드

const solution = (bridgeLength, weight, truckWeigths) => {
  let time = 0;
  let passingWeight = 0;
  let passingTrucksWeigth = [];
  let passingTrucks = [];
  let passedTrucks = [];
  let index = 0;

  while (passedTrucks.length < truckWeigths.length) {
    // 지속적인 이벤트 -1 while문 한번 돌 때 시간 +1
    time++;

    // 특별한 이벤트 1 - passingWeight가 weight보다 작은 경우 passingTrucks와 passingWeight를 더한다
    if (passingWeight + truckWeigths[index] <= weight) {
      passingTrucks.push(0);
      passingTrucksWeigth.push(truckWeigths[index]);
      passingWeight += truckWeigths[index];
      index++;
    }

    // 지속적인 이벤트 - 2 passingTrucks의 값이 0부터 시작하여 length 도달까지 +1
    for (let i = 0; i < passingTrucks.length; i++) {
      passingTrucks[i] += 1;

      // 특별한 이벤트 2 - passingTrucks 중 하나가 bridgeLength에 도달하면 passingWeight과 passingTrucks에 빼고 passedTrucks에 추가
      if (passingTrucks[i] === bridgeLength) {
        passedTrucks.push(passingTrucksWeigth[i]);
        passingWeight -= passingTrucksWeigth[i];
        passingTrucksWeigth.shift();
        passingTrucks.shift();
        i--;
      }
    }
  }

  return time + 1;
};

 

코드특징

• 지속적 이벤트와 특별한 이벤트를 나눠서 코드를 작성했다
• while문을 한 번 돌때 시간은 1씩 증가 (지속적 이벤트 1)
• 무게한계보다 낮아 트럭 한개가 진입이 가능한 경우 (특별한 이벤트 1)
  • passingTrucks[]에 0을 넣어 이를 알림.
  • passingTrucksWeight[]에 어느 트럭이 지나가고 있는지 값을 넣는다.
  • passingWeight에 현재 다리 위에 트럭들 무게의 합을 구한다. 

• passingTrucks[] 을 for문을 통해 현재 다리를 지나는 트럭들이 1씩 움직이도록 증가함 (지속적 이벤트 2)
• passingTrucks[] 내의 어느 트럭이 다리 끝에 도달하여 빠져나간 경우 (특별한 이벤트 2)
  • passedTrucks[]에 어느 트럭이 빠져나왔는지 알림
  • passingWeight에 빠져나간 트럭 무게를 뺌
  • passingTrucksWeight[]에 빠져나간 트럭을 지움 (array.prototype.shift를 활용)
  • passingTrucks[]에 빠져나간 트럭을 지움 (array.prototype.shift를 활용)
  • 트럭을 지워 돌고 있는 for문에 영향을 주기 때문에 i--

 

코드성능

• 2중 for문에 참조하는 배열들이 너무 많아 무거워진 탓에 성능이 안 좋은 것을 알 수가 있다 
• 불필요한 배열들을 삭제하여 좀 더 효율적인 코드로 수정할 필요가 있다

다른 사람 풀이법 1

function solution(bridge_length, weight, truck_weights) {
  // '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].
  let time = 0, qu = [[0, 0]], weightOnBridge = 0;

  // 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복
  while (qu.length > 0 || truck_weights.length > 0) {
    // 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면 내보내주고,
    //    다리 위 트럭 무게 합에서 빼준다.
    if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];

    if (weightOnBridge + truck_weights[0] <= weight) {
      // 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면 
      //    다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
      weightOnBridge += truck_weights[0];
      qu.push([truck_weights.shift(), time + bridge_length]);
    } else {
      // 3. 다음 트럭이 못올라오는 상황이면 얼른 큐의
      //    첫번째 트럭이 빠지도록 그 시간으로 점프한다.
      //    참고: if 밖에서 1 더하기 때문에 -1 해줌
      if (qu[0]) time = qu[0][1] - 1;
    }
    // 시간 업데이트 해준다.
    time++;
  }
  return time;
}

코드특징

• qu[][]를 통해 트럭무게와 해당 트럭이 다리 끝에 도달할 시간을 저장하여 이 둘을 핵심적으로 활용
  • 나의 코드는 프로세스 위주로 보지만 이 분은 거시적인 관점에서 보기에 더 효율적이며 깔끔하게 접근함 

• 다음 트럭이 못 올라올 경우 시간 워프를 통해 불필요하게 while문을 돌리지 않게 함

 

코드성능

• 역시 빠르다!

오늘 배운점

• 프로세스를 한번 정리하는 것은 좋다... 덕분에 풀긴풀었자너... 그러나 이에 만족하지 않고 한 번 더 생각해서 성능을 더 높일 수 있는 방안을 생각하자