다리를 지나가는 트럭

YEONGHUN KO·2021년 12월 13일
1

ALGORITHMS - PRACTICE

목록 보기
39/50
post-thumbnail

1. 트럭

다리 길이, 다리가 지탱할 수 있는 무게, 트럭무게가 담긴 배열이 주어진다. 트럭이 다리를 건너서 다 지나갈때까지 몇초가 걸리는지 리턴하면 된다. 트럭이 다리길이 1을 지나는데 1초가 걸린다고 보면된다. 예시를 통해 알아보자.

bridge_length	weight	truck_weights
  2	           10	     [7,4,5,6]

그래서 총 8초가 걸린다. 코드로 구현해보자

2. 접근 방법

위의 방법그대로 따르면 된다. 트럭하나를 뽑아서, 현재 다리가 다음 트럭의 무게를 지탱할 수 있으면 그 트럭과 나가는 시간을 qu 에다가 push한 다음, 시간이 되면 내보내는 것이다.

  • pseudo code
    • qu안에다가 첫째 트럭을 뺀다.
    • 그 트럭과 나가는 시간을 push한다.
    • 다리가 무게를 견딜 수 있을때까지.
    • 그리고 시간이 되면 다리무게에서 그 트럭의 무게를 빼고 qu에서도 빼준다.
function truck(bridge_length, weight, trucks) {
  // '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].

  let time = 0;
  let qu = [[0, 0]];
  let weightOnBridge = 0;

  // 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복

  while (qu.length > 0 || trucks.length > 0) {
    // 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면 내보내주고,
    //    다리 위 트럭 무게 합에서 빼준다.

    // ---일종의 타이머 기능이네. 그리고 시간은 알아서 흘러가게 놔둠(맨아래 time++를 뜻한다.)
    if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];

    // ---트럭이 다리위에 올라갈 수 있느냐 없느냐를 판단.
    if (weightOnBridge + trucks[0] <= weight) {
      // 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면
      //    다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
      weightOnBridge += trucks[0];
      // ---트럭 무게, 현재 시간에서 + 다리 지나가는 시간(즉 나가는 시간)을 저장해줌 큐에다가
      qu.push([trucks.shift(), time + bridge_length]);
    } else {
      // 3. 다음 트럭이 못올라오는(다리가 지탱할 수 있는 무게보다 초과) 상황이면 얼른 큐의
      //    첫번째 트럭이 빠지도록 그 시간으로 '점프'한다.
      //    time이 그 시간이 되도록 계속 기다리는 것 보다는. 그래서 반복을 최소화 한다.
      //    참고: if 밖에서 1 더하기 때문에 -1 해줌
      if (qu[0]) time = qu[0][1] - 1;
    }
    // ---시간 업데이트 해준다.
    time++;
  }

  return time;
}

3. 배운 점

  1. 트럭이 빠지는 시점으로 점프한다는게 인상깊었음.

  2. 그리고 큐에다가 트럭이랑 트럭이 나가는 시간을 저장해두고 타이밍이 맞으면 내보내는것도 인상깊었구.

  3. 각각의 트럭에 나가는 타이밍을 label해준게 인상 깊었음. 세심하게 코드를 짜는 구나 싶었다.

  4. 퉁쳐서 짜지말고 세심하게 , 최대한 모든 상황을 고려해서 짜보도록 하자.

profile
'과연 이게 최선일까?' 끊임없이 생각하기

0개의 댓글