[알고리즘] 다리를 지나는 트럭

김민기·2022년 8월 23일

알고리즘

목록 보기

3/9

문제 요약

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 한다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 한다. 다리에는 트럭이 최대 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초가 걸린다.

제한 조건

bridge_length는 1 이상 10,000 이하입니다.
weight는 1 이상 10,000 이하입니다.
truck_weights의 길이는 1 이상 10,000 이하입니다.
모든 트럭의 무게는 1 이상 weight 이하입니다.

풀이과정

문제 이해

처음 문제를 보았을 때 이해하지 못하는 부분이 많아서 문제를 이해하는데 많은 시간을 소비했다. 트럭이 다리위에 올라왔을 때 다음 카운트에서 다리를 지난 트럭으로 변경되는것이 아니라 다리 위에서 다리 길이만큼 체류한 다음 다리를 지난 트럭으로 변경된다는 점이 설명에 빠져있어서 예시로 나와있는 표를 이해하지 못했다.

혼자 정리해본바로는 아래와 같다.

시간	완료	진행	대기
0	[]	[]	[7,4,5,6]
1	[]	[7]	[4,5,6]
2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6	[7,4,5]	[6]	[]
7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

풀이 시작

구해야 하는 것은 모든 트럭이 다리를 건넜을 때 경과되는 시간이다.
1초내에 트럭이 다리를 건널 수 있고 동시에 대기열에 있는 트럭이 다리에 올라올 수 있다.
다리가 견딜 수 있는 무게에 따라 대기열에 있는 트럭을 다리에 올릴지 결정해야 한다.

큐를 사용해서 문제를 풀 수 있을거 같지만 지난번에 큐를 사용했기 때문에 이번에는 큐를 사용하지 않고 배열만 사용해서 문제를 풀어 보았다.

const totalT = truck_weight.length;
const waitT = truck_weights;
const ingT = [];
const finT = [];

대기중인 트럭은 waitT에 저장하고 진행중인 트럭을 담고 있는 ingT와 완료한 트럭을 담고 있는 finT 배열을 생성한다.
여기서 추가적으로 공부를해봐야 할 내용이 waitT = truck_weights을 실행하고 나서 truck_weights.length 를 사용해서 반복문을 종료하려 했었는데 waitT의 배열이 변경됨에 따라 truck_weights.length의 길이가 계속해서 변하는 문제가 있었다. 따라서 초기에 totalT를 만들어서 총 트럭의 숫자를 저장한다.

let cnt = 0;
while(true) {
  cnt++;
  if(ingT.length > 0){
    for(let i = 0; i < ingT.length; i++) {
      ingT[i][1]++;
    }

    if(ingT[0][1] === bridge_length) {
      finT.push(ingT[0][0])
      ingT.shift();
    }    
  }

  const ingSum = ingT.reduce((sum, pre) => {
    return sum + pre[0]
  },0);

  const rest = weight - ingSum;

  if(waitT[0] <= rest){
    ingT.push([waitT[0], 0]);
    waitT.shift(); 
  }

  if(finT.length === totalT) {
    return cnt;
  }
}

반복문을 실행하면서 우선 진행중인 트럭이 있는지 파악한다음 진행중인 모든 트럭의 체류시간을 증가시킨다. 가장 먼저 들어온 트럭이 가장 먼저 다리를 지나는 구조이기 때문에 진행중인 트럭의 가장 첫 번째 트럭의 체류시간을 확인해서 다리 길이만큼 다리에 있었다면 완료한 트럭의 배열로 이동시킨다.

reduce를 사용해서 진행중인 트럭의 모든 무게를 합한 값을 구한다. 그리고 그 값과 다리가 버틸수 있는 무게를 사용해서 대기열 가장 앞에 있는 트럭이 건널 수 있는 무게라면 대기열에 있는 트럭을 진행중인 트럭으로 이동시킨다.

이 과정을 계속해서 반복하면서 마지막으로 완료한 트럭을 담고 있는 배열의 길이와 초기에 구해두었던 모든 트럭의 수를 비교해서 일치한다면 카운트를 리턴한다.