[ JavaScript ] 프로그래머스 level2 42583번 다리를 지나는 트럭

다리를 지나는 트럭 #42583

프로그래머스 알고리즘 고득점 Kit > 스택/큐 > level2 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

입출력 예bridge_lengthweighttruck_weightsreturn

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

처음에 문제가 이해가 가지 않아서 여러번 읽어보고, 출처도 읽어보았다. 

프로그래머스 내의 설명이 조금 부족한 것 같기도 했다. 

출처를 읽었을 떄 이해한 것은 bridge_length는  트럭 하나가 건너려면 걸리는 시간을 뜻하는 것 같았다. 

 

첫번째 입출력 예를 그림/표로 그려본다면 아래와 같다. 

나의 풀이

function solution(bridge_length, weight, truck_weights) {
  let sec = 0; // 총 걸리는 시간

  const size = truck_weights.length; // 전체 트럭의 수

  const wait = truck_weights; // 대기 중인 트럭 배열
  const bridge = []; // 다리 위인 트럭 배열 [weight,지나온 길이]
  const finish = []; // 다리를 벗어난 트럭 배열

  let weightOnBridge = 0; // 다리 위 트럭들의 무게 합

  // 다리를 벗어난 트럭의 갯수가 총 트럭의 갯수보다 작을 때만 아래를 반복함
  while (finish.length < size) {
    // 다리의 가장 앞에 있는 트럭이 지나온 길이가 다리의 길이와 같으면 finish로 이동
    if (bridge.length > 0 && bridge[0][1] == bridge_length) {
      weightOnBridge -= bridge[0][0];
      finish.push(bridge.shift());
    }

    // 다리 위 무게 + 들어갈 트럭의 무게가 한계값보다 작거나 같으면
    // 다리에 트럭을 push하고, wait 배열에서 제거
    if (weightOnBridge + wait[0] <= weight) {
      bridge.push([wait[0], 0]);
      weightOnBridge += wait[0];
      wait.shift();
    }

    sec++; // 시간이 1초 증가되면
    bridge.forEach((el) => el[1]++); // 다리 위 트럭들이 지나온 길이가 1 증가한다.
  }

  return sec;
}

• 총 걸리는 시간 변수 sec
• 전체 트럭의 개수 size 
• 대기 중인 트럭 배열 wait
• 다리 위인 트럭 배열 bridge
  • bridge 배열의 값들은 [weight,지나온 길이] 형태로 push된다. 
• 다리를 벗어난 트럭 배열 finish
• 다리 위 트럭들의 무게의 합 weightOnBridge

를 선언한다.

• 다리를 벗어난 트럭의 개수가 총 트럭의 수와 같으면 모든 트럭이 다리를 벗어난 상태이므로 그때까지 반복한다.
• 다리 위 트럭 중 가장 앞에 있는 트럭이 지나온 길이가 다리의 길이와 같으면 다 건넌 것이므로 finsish 배열로 이동한다. 
• 다리 위 무게에 들어갈 트럭의 무게 값을 더한 것이 한계값을 넘지 않으면
  bridge에 트럭을 넣고, wait에서 제거한다. 
• 시간을 1초 증가시키고,
• 다리 위 트럭들의 지나온 길이도 1씩 증가시킨다. 

다른 풀이

function solution(bridge_length, weight, truck_weights) {
  let sec = 0; // 걸리는 시간
  let bridge = [[0, 0]]; // 다리 위 트럭 [무게, 빠져나가는 시간]
  let weightOnBridge = 0; // 다리 위 총 무게

  while (bridge.length > 0 || truck_weights.length > 0) {
    // 다리의 첫 트럭의 빠져나가가는 시간이 현재 시간과 같으면 다리에서 제거
    if (bridge[0][1] === sec) {
      weightOnBridge -= bridge.shift()[0];
    }

    // 다리 위 무게 + 들어갈 트럭이 한계 무게를 넘지 않으면
    // 다리에 트럭을 추가
    if (weightOnBridge + truck_weights[0] <= weight) {
      weightOnBridge += truck_weights[0];
      bridge.push([truck_weights.shift(), sec + bridge_length]);
    } else {
      // 트럭을 더 넣을 수 없으면, 현재 시간을 다리의 첫 트럭이 빠져나가는 시간으로 jump
      // 1을 빼주는 이유는, if문 밖에서 시간 증가가 이루어지기 때문
      if (bridge[0]) sec = bridge[0][1] - 1;
    }

    sec++; // 시간 1초 증가
  }

  return sec;
}

 나의 풀이와의 차이점들은

• finish 배열 x 
• bridge 배열의 값들의 두번째 값을 지난 다리의 길이가 아닌, 빠져나가는 시간으로 저장한 것 
  • 지나온 다리의 길이로 넣었을 때는 시간이 지날때마다 하나씩 증가시켜주었어야 했음
• 트럭을 더 넣을 수 없을 때 계속 시간을 1씩 증가시키면 루프를 돌지 않고, 현재 시간을 jump함

 

트럭의 수가 늘어날때마다 효율성의 차이가 크게 드러난다. 

나의 풀이에서는 걸리는 초만큼 무조건 while을 돌게되는 반면에, 

다른 풀이에서는 걸리는 시간을 jump했기 때문이다.