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

Chloé·2022년 3월 14일

JavaScript 알고리즘 프로그래머스

JavaScript 알고리즘 with 프로그래머스

목록 보기

7/8

다리를 지나는 트럭 #스택/큐

출처 - 프로그래머스 코딩테스트 고득점 KIT

💡 문제 접근하기

큐를 이용하여 다리의 현재 상태를 재현한다는 발상으로 접근할 때 빠르고 깔끔하게 풀린다!

입력값으로 주어진 다리의 길이만큼의 길이를 가진 배열 bridge를 생성한다.
- 이 배열은 다리의 현재 상태를 나타낸다.
  - 배열의 0번 인덱스가 다리의 도착 지점이고, -1번 인덱스가 다리의 출발 지점이다.
  - 다음 트럭이 다리에 올라가면 다리의 -1번 인덱스에 추가된다.
  - 트럭은 매 초 한 칸씩 앞으로 이동한다. 즉, 인덱스가 하나씩 감소한다.
- 처음에는 다리 위에 아무 트럭도 올라가 있지 않으므로 배열의 모든 요소는 0으로 초기화한다.
- 배열의 끝에 새로운 요소를 추가하고, 배열의 맨 앞 요소를 꺼낼 것이므로 이 배열은 큐!
현재 다리 위에 올라간 트럭의 하중을 나타내는 변수 bridge_sum을 생성한다.
- 처음에는 다리 위에 아무 트럭도 올라가 있지 않으므로, 0으로 초기화한다.
1초가 지났다. 첫 트럭을 다리의 출발 지점에 올린다.
- 소요시간을 나타내는 answer를 1 증가시킨다.
- truck_weights 배열의 맨 첫 요소가 첫 트럭이 된다.
  - bridge 배열의 끝에 이 요소를 push()하고,
  - bridge_sum에 이 요소를 더한다.
- 다리 전체의 길이를 유지하기 위해 bridge 배열의 맨 첫 요소를 shift() 한다.
다리 위에 트럭이 올라가 있는 동안, 즉 다리의 현재 하중(bridge_sum)이 0보다 클 동안 반복하여:
- 우선 시간을 1초 증가시키고,
- 다리의 맨 앞 요소를 shift()하고, 해당 요소만큼의 값을 bridge_sum에서 빼준다.
- 현재 다리의 하중(bridge_sum)에 다음 트럭의 무게(truck_weight[0])를 더했을 때 다리가 견딜 수 있는 전체 무게(weight)보다 작거나 같다면,
  - 다음 트럭을 bridge 배열에 push()하고, bridge_sum에 더한다.
- 만약 전체 무게보다 크다면, 다음 트럭이 올라갈 수 없다는 뜻이므로,
  - bridge 배열에 0을 push()한다.
다리의 현재 하중이 0이 되는 순간, 즉 모든 트럭이 다리를 다 건넌 순간 answer를 반환한다.

🔥 문제 풀어보기

정석대로 큐를 이용해 풀어보기

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());
  
  // 대기 트럭 배열이 남아있거나 다리 위에 올라간 트럭 배열이 남아있는 동안,
  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;
}

시뮬레이션으로 풀어보기

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

  // 다리 위에 올라간 트럭 배열
  let bridge = [];
  // 현재 시점 다리에 걸린 하중
  let bridge_sum = 0;

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

    // 다리 위에 올라가 있는 트럭들의 위치를 1씩 증가시키고,
    bridge = bridge.map(([truck, location]) => [truck, location + 1]);

    // 만약 다리 위에 트럭이 있는데 그 트럭 중 맨 앞 트럭의 위치가 다리를 지난 다음이라면,
    if (bridge.length > 0 && bridge[0][1] > bridge_length) {
      // 다리 배열에서 그 트럭을 빼고 그 트럭의 무게도 다리 하중에서 제외한다.
      bridge_sum -= bridge.shift()[0];
    }

    // 만약 현재 시점 다리 하중에 다음 트럭의 무게를 더해도 다리가 버틸 수 있다면?
    if (truck_weights.length > 0 && bridge_sum + truck_weights[0] <= weight) {
      // 다음 트럭을 다리 배열에 넣고 초기값으로 1의 위치를 지정해준다. 현재 시점 하중에 트럭 무게를 더해준다.
      let truck = truck_weights.shift();
      bridge.push([truck, 1]);
      bridge_sum += truck;
    }
  }

  return answer;
}

문제가 스택/큐로 분류되어 있으므로, 큐를 이용하면 간단하게 해결될 수 있는 문제였는데..., 그 큐를 어떻게 설정해야 할 지 떠오르지 않았다. 그래서 각 트럭을 [무게, 현재 다리 위의 위치] 로 표기해 사실상 시뮬레이션으로 접근해 풀었다.
본문의 풀이방식은 다리 큐의 길이가 늘 다리의 길이만큼으로 일정한 반면, 이렇게 풀게 되면 다리 배열의 길이가 늘 달라지기 때문에 인덱스 에러를 방지하기 위해 매번 조건문을 한 번 더 걸어줘야 하기 때문에 번거롭고,
다리 배열을 매번 map하여 새로 생성하기 때문에 시간과 메모리 소요가 크다.