[Lv2] 다리를 지나는 트럭

Creating the dots·2022년 1월 21일
0

Algorithm

목록 보기
55/65

프로그래머스

문제 예시를 보면 경과 시간이 1~2초인 경우가 있다. 왜 한번에 2초가 소요되는지가 문제의 포인트인데, 다리가 bridge_length만큼의 칸이 있다는 것을 알 수 있다.

그래서 초가 카운트되는 경우는, 트럭이 한칸씩 이동할때이므로, 예시에서는 [0,7]일때 한번, [7,0]일때 한번씩 카운트되어 2초가 소요된다.

나의 풀이

수도코드

  • 다리는 bridge_length만큼의 요소를 가진 배열이므로, 초기값으로 bridge_length만큼의 요소를 가진 배열(onBridge)로 저장한다.
  • sum은 다리에 올라가있는 트럭의 총 무게이다.
  • count는 모든 트럭이 다리를 건너는데 걸리는 초이다.
  • 다리위에 트럭이 없을때까지 반복문 실행
    • 올라갈 트럭의 무게를 truck에 저장한다. 더이상 트럭이 없다면 0
    • 가장 첫 칸의 트럭을 빼고 전체 무게에서도 뺀다.
    • 다리 위의 트럭 무게 총합에 따라 분기
      • 다리 위에 트럭이 올라갈 수 없는 경우
        • 올라갈 트럭의 무게(truck)를 다시 되돌려놓기
        • 한칸씩 이동만 할 수 있으므로 0을 푸시한다(truck_weights.unshift(truck))
        • 한칸씩 이동했으니까 1초 추가
      • 다리 위에 트럭이 올라갈 수 있는 경우
        • 트럭의 무게가 0보다 크면 트럭을 푸시하고, 다리의 총 무게에도 더해준다.
        • 트럭의 무게가 0이면, 더이상 다리에 올라가지 않아도 된다.
        • 두 가지 경우 모두 트럭이 한 칸씩 이동한 것이므로 1초 추가
function solution(bridge_length, weight, truck_weights) {
  const onBridge = new Array(bridge_length).fill(0);
  let sum = 0;
  let count = 0;
  
  while(onBridge.length>0) {
    const truck = truck_weights.shift() || 0;
    const off = onBridge.shift();
    sum -= off;
    
    if(sum+truck > weight) {
      onBridge.push(0);
      truck_weights.unshift(truck);
      count++;
    }
    else if(sum+truck <= weight) {
      if(truck > 0){
        onBridge.push(truck);
        sum += truck;
      }
      count++;
    }
  }
  return count;
}   

다른 분의 풀이

function solution(bridge_length, weight, truck_weights) {
  let time = 0, qu = [[0,0]], weigthOnBridge = 0;
  
  while(qu.length > 0 || truck_weights.length > 0) {
    if(qu[0][1] === time) weightOnBridge -= qu.shift()[0];
    
    if(weightOnBridge + truck_weights[0] <= weight) {
      weightOnBridge += truck_weights[0];
      qu.push([truck_weights.shift(), time+bridge_length]);
    } else{
      if(qu[0]) time qu[0][1]-1;
    }
    time++;
  }
  return time;
}       
profile
어제보다 나은 오늘을 만드는 중

0개의 댓글