[프로그래머스 Lv2] 다리르 지나는 트럭

https://school.programmers.co.kr/learn/courses/30/lessons/42583

이전 스택문제처럼 반복문을 중첩해서 돌리면 풀 수 있을 것이다. 하지만, 제한조건들이 모두 1~10000 이므로 시간복잡도를 고려해야 한다. 일단 트럭을 다리에 올리면서 처음에 들어간 트럭을 빼야 한다. 따라서 큐를 생각해 볼 수 있는데 구현이 쉽지 않아서 구글링 했다.

문제 접근

1. 모두 0으로 이루어진 다리 길이만큼의 길이를 가진 배열 bridge 생성
   -> 만약 다리길이가 5이면 [0, 0, 0, 0, 0]
   -> 0번 인덱스는 도착 지점, 맨끝 인덱스는 다리의 출발 지점이다. 따라서, push()를 통해서 트럭을 다리에 올리고, shift()를 통해서 다리에서 트럭을 빼는 queue 자료구조이다.
   예를들어 다리길이가 5이고, 무게가 3인 트럭 하나를 올린다면, [0,0,0,0,3], [0,0,0,3,0],[0,0,3,0,0],[0,3,0,0,0],[3,0,0,0,0] 이런식으로 매초마다 트럭이 움직인다. 물론 매초마다 출발지점에 무게를 고려하여 트럭을 다리에 더 올릴 수 있는지 고려해야 한다.

2. 현재 다리가 책임지고 있는 무게를 bridge_sum 생성
   -> 0으로 초기화, 만약 처음을 제외하고 이 값이 0이면 리턴(모든 트럭 지나감)

3. 소요시간을 나타내는 answer 생성

전체적인 흐름

입력값은 (2, 10, [7, 4, 5, 6])로 가정하자. 차례대로(다리의 길이, 다리가 견딜 수 있는 무게, 트럭 무게 배열)

1. 처음에 우선 1초가 흘러 다리에 트럭을 올리고, 하중을 올리고, 소요시간을 증가시킨다. 여기서 주의할 점은 bridge배열인데 [0, 0, 7]이 되면 다리 길이가 3이 되므로, 항상 다리 길이를 2로 유지하기 위해 bridge.shift()를 하고 bridge.push()를 통해 [0,7]을 만든다. 이러면 다리 출발 지점에 트럭이 올라간 것이다.

이후에는

1. 소요시간 증가
2. 다리 배열의 맨 앞을 꺼내서 하중을 줄인다.
3. while문으로 더이상 들어갈 트럭이 있고, 다리에 트럭을 더 올릴 수 있으면 다음 트럭을 다리의 출발 지점에 넣고, 하중을 증가시킨다. 올릴 수 없다면 bridge에 0을 추가한다.(트럭을 앞당기는 역할을 한다.) 예를들어 [0,7] -> [7,0]
4. 1~3번 반복

풀이

function solution(bridge_length, weight, truck_weights) {
  let answer = 0;

  // 다리 위에 올라간 트럭 배열
  let bridge = Array.from({ length: bridge_length }, () => 0);
  // 현재 시점 다리에 걸린 하중
  let bridge_sum = 0;

  // 1초를 증가시키고, 맨 처음 트럭을 다리에 올린다.
  answer++;
  bridge.shift();
  bridge_sum += truck_weights[0];
  bridge.push(truck_weights.shift());
  bridge;

  // 대기 트럭 배열이 남아있거나 다리 위에 올라간 트럭 배열이 남아있는 동안,
  while (bridge_sum > 0) {
    // 우선 시간이 1초 지났을 때,
    answer++;

    // 큐의 맨 앞을 꺼내고,
    bridge_sum -= bridge.shift();

    // 만약 현재 시점 다리 하중에 다음 트럭의 무게를 더해도 다리가 버틸 수 있다면?
    if (truck_weights.length > 0 && bridge_sum + truck_weights[0] <= weight) {
      // 다음 트럭을 다리 배열에 넣는다.
      bridge_sum += truck_weights[0];
      bridge.push(truck_weights.shift());
    } else {
      bridge.push(0);
    }
  }

  return answer;
}