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

2022. 9. 1. 15:59·알고리즘
반응형

문제 설명

 

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

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

제한 조건

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

입출력 예

2 10 [7,4,5,6] 8
100 100 [10] 101
100 100 [10,10,10,10,10,10,10,10,10,10] 110

 

나의 풀이

const bridge_length = 100;
const weight = 100;
const truck_weights = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10];

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;

    return value;
  }

  peek() {
    return this.queue[this.front][0];
  }

  size() {
    return this.rear - this.front;
  }

  weight() {
    return this.queue.reduce((prev, current) => prev + current[1], 0);
  }

  upTime() {
    this.queue = this.queue.map((data) => {
      return [data[0] + 1, data[1]];
    });
  }
}

function solution(bridge_length, weight, truck_weights) {
  var answer = 1;

  const queue = new Queue();

  queue.enqueue([1, truck_weights.shift()]);

  while (queue.size() !== 0) {
    answer++;
    queue.upTime();

    if (queue.peek() > bridge_length) {
      queue.dequeue();
    }

    const currentWeight = queue.weight();
    const size = queue.size();
    const newWeight = truck_weights[0];

    if (currentWeight + newWeight <= weight && size < bridge_length) {
      queue.enqueue([1, truck_weights.shift()]);
    }
  }

  return answer;
}

solution(bridge_length, weight, truck_weights);

이전에 공부했던 Queue를 활용해서 문제를 쉽게 풀었다. 

 

문제는 쉽게 풀었지만,  초당 트럭이 얼마나 움직이는지에 대한 설명이 없어서  문제 자체를 이해하는 건 오래 걸렸다....

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[알고리즘] 카펫  (1) 2022.09.03
[알고리즘] H-Index  (2) 2022.09.02
[알고리즘] 2 x n 타일링  (0) 2022.08.31
[알고리즘] 배달 - 다익스트라 알고리즘  (0) 2022.08.30
[알고리즘] 소수 범위 구하기  (1) 2022.08.24
'알고리즘' 카테고리의 다른 글
  • [알고리즘] 카펫
  • [알고리즘] H-Index
  • [알고리즘] 2 x n 타일링
  • [알고리즘] 배달 - 다익스트라 알고리즘
잉여개발자
잉여개발자
풀스택 개발자를 목표로 잉여롭게 개발 공부도 하면서 다양한 취미 생활도 즐기고 있는 잉여 개발자입니다.
  • 잉여개발자
    잉여로운 개발일지
    잉여개발자
    • 분류 전체보기 (789)
      • 개발정보 (36)
      • 개발환경 (7)
      • 개발생활 (19)
      • React (141)
        • 이론 (23)
        • 기능 (12)
        • 실험실 (88)
        • 버그 (6)
        • 패스트캠퍼스 (9)
        • Npm (3)
      • React Native (28)
        • 공통 (6)
        • TypeScript (3)
        • JavaScript (18)
        • 버그 (1)
      • Next.js (30)
        • 이론 (13)
        • 실험실 (13)
        • 버그 (3)
      • Web (35)
      • 알고리즘 (202)
        • 풀이 힌트 (39)
      • JavaScript (47)
      • TypeScript (29)
        • 기초 (27)
        • 실험실 (2)
      • Node.js (13)
        • 이론 (0)
        • 기능 (3)
        • 실험실 (9)
        • 버그 (1)
      • 도커 (4)
      • CCNA (22)
        • 이론 (4)
        • 문제 (18)
      • 취미생활 (167)
        • 잉여로운 칵테일 (2)
        • 잉여의 식물키우기 (130)
        • 잉여로운 여행기 (11)
        • 잉여의 제2외국어 (21)
        • 잉여로운 책장 (2)
      • Java (1)
        • Java의 정석 (1)
      • 꿀팁 공유 (3)
  • 태그

    typescript
    리얼학습일기
    바질 키우기
    CCNA
    Docker
    react
    javascript
    프로그래머스
    덤프
    식물
    영어회화
    CSS
    redux
    ReactNative
    알고리즘
    리액트
    자바스크립트
    네트워크
    next.js
    ChatGPT
    타입스크립트
    webpack
    다이소
    영어독학
    바질
    Node.js
    네이버 부스트캠프
    리얼클래스
    Babel
    타일러영어
  • hELLO· Designed By정상우.v4.10.1
잉여개발자
[알고리즘] 다리를 지나는 트럭
상단으로

티스토리툴바