Programmers - 스택/큐 > 다리를 지나는 트럭

내 풀이

처음에 문제 이해하는 것 부터가 난관이였다. 예시를 이해하는 것 부터가 어려워서 시간이 꽤 걸렸다. 예시를 이해하고 나서는 논리적으로 풀 수 있는 방법을 계속 고민했는데 너무 깊게 파고들다보니 문제가 어려워지기 시작했다. 결국 시간 내로 문제를 풀지 못했다.(L1: 30분, L2: 1시간, L3: 1시간 30분)

1-1. 현재 bridge에 올라가있는 트럭들의 무게와 truck_weight[0] 무게의 합이 weight보다 작을 경우에만 현재 bridge에 올린다.
1-2. 만약 weight보다 클 경우 현재 bridge의 첫번째 요소를 빼고 다시 현재 bridge와 truck_weight[0]의 무게를 합하여 weight과 비교한다.
2. 1대 빠질 때마다 1의 과정을 반복한다.

function solution(bridge_length, weight, truck_weights) {
  let result = 0;
  let currentBridge = [];
  let truck = 0;
  let bridgeSum = 0;
  let isDuo = 0;

  while (truck_weights) {
    bridgeSum = truck_weights.reduce((pre, cur) => pre + cur, 0);
    if (
      bridgeSum + truck_weights[0] <= 10 &&
      currentBridge.length + 1 <= weight
    ) {
      truck = truck_weights.shift();
      currentBridge.push(truck);
      result++;

    } else {
      result += bridge_length - currentBridge.length;
      currentBridge.shift();
    }
  }
}

모범답안

이차원 배열을 활용하여 한 truck에 [트럭무게, 이 트럭이 나갈 시간]의 속성을 부여한다.
1. 현재 시간이 큐 맨 앞의 트럭의 나갈 시간과 같다면 내보내주고, 다리 위 트럭 무게 합에서 뺀다.
2. 다리 위 트럭 무게 합 + 대기 중인 트럭의 첫 무게가 감당 무게 이하면 다리 위 트럭 무게 업데이트, 큐 뒤에 [truck_weight.shift(), time + bridge_length] 추가
3. 다음 트럭이 못올라오는 상황이면 큐의 첫번째 트럭이 빠지도록 그 시간으로 점프

function solution(bridge_length, weight, truck_weights) {
  // '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].
  let time = 0, qu = [[0, 0]], weightOnBridge = 0;

  // 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복
  while (qu.length > 0 || truck_weights.length > 0) {
    // 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면 내보내주고,
    //    다리 위 트럭 무게 합에서 빼준다.
    if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];

    if (weightOnBridge + truck_weights[0] <= weight) {
      // 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면 
      //    다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
      weightOnBridge += truck_weights[0];
      qu.push([truck_weights.shift(), time + bridge_length]);
    } else {
      // 3. 다음 트럭이 못올라오는 상황이면 얼른 큐의
      //    첫번째 트럭이 빠지도록 그 시간으로 점프한다.
      //    참고: if 밖에서 1 더하기 때문에 -1 해줌
      if (qu[0]) time = qu[0][1] - 1;
    }
    // 시간 업데이트 해준다.
    time++;
  }
  return time;
}

내 풀이와 차이점

쉽게 풀려는 고민을 너무 깊게한 탓에 문제 자체를 풀지 못하고 시간을 다썼다. 모범 답안은 문제를 있는 그대로 흐름에 따라 풀었다.

얻어갈 부분

쉽게 푸는 방법을 고민하는 것은 당연 중요하지만, 있는 그대로 흐름을 따라가는 방법도 나쁜 방법은 아니다. 쉽게 푸는 방법을 10분 간 고민한 뒤 안떠오를 경우에는 흐름에 따라 무식하게 풀자!