[프로그래머스/레벨2] 다리를 지나는 트럭 (자바스크립트)

[프로그래머스/레벨2] 다리를 지나는 트럭 (자바스크립트)

문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

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

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

 

입출력 예

 

문제 해결 방법

• 다리의 길이만큼의 length를 가지는 bridge 큐(또는 배열)을 생성합니다. 초기값으로 0을 채워넣습니다.
• while문을 사용합니다. 조건은 bridge 큐의 length가 0이 아닐 때까지입니다.
• bridge 큐의 첫 번째 원소는 바로 도착할 트럭을 나타내므로 dequeue 합니다.
• bridge 큐의 총합이 weight(다리가 견딜 수 있는 무게)를 넘지 않으면 truck_weights에서 앞 부분을 shift(맨 앞 원소를 반환하고 배열에서 제거)한 후, bridge 큐에 해당 무게의 truck을 enqueue 합니다.
• 만약 다리 큐의 총합이 weight를 초과한다면 bridge 큐에 0을 enqueue 합니다.
• 이런 식으로 진행하면, 도착한 트럭이 늘어날수록 bridge의 length는 줄어들 것이며 0이 되는 순간 반복문은 종료됩니다.
• 이 문제는 효율성이 채점 항목이 아니기 때문에 별도로 큐를 구현하지 않고 배열의 shift(), push() 기능을 dequeue, enqueue를 대신해 사용하여도 아무 문제가 없습니다. 다만 이렇게 하면 계산 시간이 천 단위를 넘어가기 때문에 만약 효율성도 채점 항목이라면 수동으로 구현된 queue 를 사용해야 합니다.  (저는 큐를 만들 줄 몰라서 다른 사이트에서 퍼왔습니다.)

 

코드

큐 자료구조 - 출처 바로가기

// https://velog.io/@ansrjsdn/JS-Queue-%EA%B5%AC%ED%98%84%ED%95%B4%EB%B3%B4%EA%B8%B0
//  각각의 노드, 노드의 data와 다음 노드를 가리키고 있다.
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// 큐 클래스
class Queue {
  constructor() {
    this.head = null; // 제일 앞 노드
    this.rear = null; // 제일 뒤 노드
    this.length = 0; // 노드의 길이
    this.sum = 0 // **데이터는 전부 숫자라고 가정
  }

  enqueue(data) { // 노드 추가.
    const node = new Node(data); // data를 가진 node를 만들어준다.
    if (!this.head) { // 헤드가 없을 경우 head를 해당 노드로
      this.head = node;
    } else {
      this.rear.next = node; // 아닐 경우 마지막의 다음 노드로
    }
    this.rear = node; // 마지막을 해당 노드로 한다.
    this.length++;
    this.sum += data // **데이터는 전부 숫자라고 가정
  }

  dequeue() { // 노드 삭제.
    if (!this.head) { // 헤드가 없으면 한 개도 없는 것이므로 false를 반환.
      return false;
    }
    const data = this.head.data; // head를 head의 다음 것으로 바꿔주고 뺀 data를 return
    this.head = this.head.next;
    this.length--;

    this.sum -= data // **데이터는 전부 숫자라고 가정
    return data;
  }
  // head를 반환하는 함수
  front() { // head가 있을 경우 head의 data를 반환.
    return this.head && this.head.data;
  }
  //큐의 모든 원소를 반환하는 함수
  getQueue() {
    if (!this.head) return false;
    let node = this.head;
    const array = [];
    while (node) { // node가 없을 때까지 array에 추가한 후 반환해준다.
      array.push(node.data);
      node = node.next;
    }
    return array;
  }
}

 

문제 해결 부분

function solution(bridge_length, weight, truck_weights) {

    if(truck_weights.length == 1) {
        return bridge_length + 1
    }

    let second = 0
    let bridge = new Queue()
    for(let i = 0; i < bridge_length; i++) {
        bridge.enqueue(0)
    }

    while(bridge.length) {
        second++
        bridge.dequeue()
        if(truck_weights.length) {
            const sumOfBridge = bridge.sum
            if(sumOfBridge + truck_weights[0] <= weight) {
                bridge.enqueue(truck_weights.shift())
            } else {
                bridge.enqueue(0)
            }
        }
    }
    
    return second
}

 

참고) 자바스크립트 배열 사용

function solution(bridge_length, weight, truck_weights) {

    if(truck_weights.length == 1) {
        return bridge_length + 1
    }

    let second = 0
    let bridge = new Array(bridge_length).fill(0)

    while(bridge.length) {
        second++
        bridge.shift()
        if(truck_weights.length) {
            const sumOfBridge = bridge.reduce((acc, val) => acc + val, 0)
            if(sumOfBridge + truck_weights[0] <= weight) {
                bridge.push(truck_weights.shift())
            } else {
                bridge.push(0)
            }
        }
    }
    return second
}