jiho_bae
Go devlog
jiho_bae
전체 방문자
오늘
어제
  • 분류 전체보기 (158)
    • JavaScript (38)
      • theory (34)
      • vanilla (4)
    • HTML & CSS (2)
    • Browser (3)
    • CS (6)
      • linux (1)
      • shell (2)
      • compiler (2)
    • DS & Algorithm (87)
      • theory (5)
      • basic (7)
      • programmers (30)
      • baekjoon (45)
    • Design Pattern (2)
    • Error (4)
    • Git & Github (4)
    • Tools (1)
    • 부트캠프 (4)
    • Small Tips (2)
    • Java (3)
    • test (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 가사 검색 자바스크립트
  • 자바스크립트 비동기 마이크로 태스크 큐와 렌더링 과정
  • 병합정렬 자바스크립트
  • 백준 17406 nodeJS
  • 자바스크립트 채팅방 스크롤
  • 덧칠하기 javascript
  • 백준 자바스크립트 입력 템플릿
  • 계수정렬 자바스크립트
  • safari Date format NaN
  • 대충만든자판 javascript
  • 13460 javascript nodejs
  • 외벽 점검 javascript
  • 리코쳇 로봇 javascript
  • 자바스크립트 모듈 시스템
  • 1753 최단경로 javascript
  • 카카오 코딩테스트 양궁대회 nodeJS
  • 자바스크립트 sort는 왜 그모양일까
  • safari invalid date error
  • 자바스크립트 이벤트 위임
  • 25632 소수 부르기 게임
  • 퀵정렬 자바스크립트
  • javascript use strict
  • 프로그래머스 숫자카드나누기 javascript
  • 억억단을 외우자 javascript
  • fetch 취소하기
  • 리액트 프로젝트 디버깅하기
  • 깃 이전 커밋에서 새 브랜치 만들기
  • 자바스크립트 배열의 특수함
  • 자바스크립트 커링
  • JavaScript

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
jiho_bae

Go devlog

[프로그래머스] 다리를 지나는 트럭 - 자바스크립트
DS & Algorithm/programmers

[프로그래머스] 다리를 지나는 트럭 - 자바스크립트

2021. 4. 19. 17:31

문제

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

입출력 예시

첫 풀이

요약

트럭은 정해진 순서대로 다리를 건넌다.
다리를 건너는 트럭 무게의 총합은 다리가 견딜 수 있는 무게를 넘을 수 없다.
모든 트럭이 완전히 다리를 건너야 한다.
트럭은 1초에 1씩 다리 위를 움직인다.

 

첫 풀이 방법

우선 다리를 건너고 있는 트럭 무게를 위한 Queue 자료구조를 선언한다.
그리고 다리를 건너고 있는 트럭의 시간을 위한 큐를 선언한다.
자바스크립트에는 별도의 Queue 자료형이 없으므로, 배열을 선언하고 shift, push 메소드를 사용 할 것.

대기중인 트럭이 다리를 건널 수 있는지, 각 초마다 다리에 있는 트럭의 총 무게를 조사한다.
모든 트럭은 1초에 1만큼만 움직이므로, 각 트럭마다 건너는 시간은 다리의 길이와 같다. 그러므로 별도로 선언한 시간 큐를 이용한다.
큐의 맨 처음 시간이 가장 먼저 다리를 지나는 트럭의 시간이므로 그 시간이 다리의 길이와 같을 때 큐에서 트럭을 빼준다.
다리 건너기를 대기하고 있는 트럭이 없고, 큐에 트럭이 존재하지 않을 때 반복문이 종료된다.

function solution(bridge_length, weight, truck_weights) {
  const truckQueue = []; // 각 트럭 무게를 위한 큐
  let timeQueue = []; // 각 트럭이 다리를 건너는 시간을 위한 큐
  let totalTime = 0; // 총 건너는 시간
  let weightSum = 0; // 다리를 건너는 중인 트럭 무게들의 합

  while (true) {
    if (weightSum + truck_weights[0] <= weight) {
      const tWeight = truck_weights.shift();
      truckQueue.push(tWeight);
      weightSum += tWeight;
      timeQueue.push(0);
    } 
    // 다리에 있는 트럭 무게 합 + 대기중인 트럭 무게 <= 다리가 견디는 트럭 무게라면
    // 대기중인 트럭 무게를 tWeight에 넣어주고, 무게 큐에 넣고, 
    // 다리를 건너는 트럭 무게 합을 늘려주고 시간 큐에 0을 넣어준다.

    timeQueue = timeQueue.map((time) => time + 1);
    totalTime++;
    // 1초에 1씩 이동하므로 각 시간을 1씩 늘려주고, 총 건너는 시간을 1 늘린다.    

    if (timeQueue[0] === bridge_length) {
      weightSum -= truckQueue.shift();
      timeQueue.shift();
      // 다리 가장 앞에 있는 트럭의 이동시간이 다리의 길이와 같으면 다리의 끝에 위치하므로
      // (아직 다리를 완전히 다 건넌 것이 아니다.) 각 큐에서 첫번째 값을 빼준다.
      if (truck_weights.length === 0 && timeQueue.length === 0) break;
      // 만약 대기중인 트럭이 없고, 다리를 지나는 중인 트럭도 없다면 while문을 탈출한다.
    }
  }
  return totalTime + 1;
  // while을 break로 탈출할 때 사실 트럭이 다리 끝에 위치한 시점에 탈출한 것이므로, 
  // 1초를 더해줘야 완전히 다리를 지난 시간이다.
}

코드 정리해보기

다음과 같이 코드를 짜면 정답은 잘 나온다.
무작정 코드를 쓰다 보니 불필요한 코드가 많아진 것 같아서, 내가 짠 코드를 가지고 조금 정리해 보겠다.

  1. 큐를 두개 씩이나 쓸 필요는 없어보인다. 큐를 하나만 선언하고 큐에 트럭을 push할 때, [weight, time] 배열을 넣자.
    사실 이것 하나만으로 코드가 꽤나 간단해 질 것 같아서 기대된다.
  2. while 조건문에 true 대신 구체적인 탈출조건을 명시해보자.
function solution(bridge_length, weight, truck_weights) {
  let queue = []; // 하나의 큐 선언
  let totalTime = 0; // 총 건너는 시간
  let weightSum = 0; // 다리를 건너는 중인 트럭 무게 합

  while (truck_weights.length !== 0 || queue.length !== 0) { 
      // 이렇게 선언하면 둘 다 0이어야 while문을 탈출한다.
    if (weightSum + truck_weights[0] <= weight) {
      const tWeight = truck_weights.shift();
      queue.push([tWeight, 0]);
      weightSum += tWeight;
    } 
    // 대기중인 트럭이 다리를 건널 수 있으면 [weight, time] 형태로 큐에 넣고, 
    // 다리를 건너는 트럭 무게 합을 증가시킴
    queue = queue.map(([w, t]) => [w, t + 1]);
    totalTime++;
    // 각 트럭들의 시간과 총 소요 시간을 1회 반복당 1씩 늘린다.
    if (queue[0][1] === bridge_length) {
      weightSum -= queue.shift()[0];
    } // 맨 앞 트럭의 시간이 길이와 같으면 트럭이 다리 끝에 위치했으므로(아직 건너지 않았다)
      // 큐에서 빼주고, 다리를 건너는 트럭 무게 무게를 줄여준다.
      // (우선 빼줘야 다음 반복 때 대기 중인 트럭의 출발 여부를 판단한다.)
  }
  return totalTime + 1; 
      // 마지막으로 다리를 건너는 트럭이 다리 끝에 위치할 때 while문이 종료되므로
      // 1초 후에 완전히 트럭이 다리를 건넌다. 
}

이해를 돕기 위한 주석을 추가해둬서 좀 지저분하지만, 그래도 전보다는 더 이해하기 쉬운 코드가 된 것 같다.
단순 제 지식으로만 해결했을 뿐 더 효율적인 코드가 존재할 수 있습니다.

저작자표시 (새창열림)

'DS & Algorithm > programmers' 카테고리의 다른 글

[프로그래머스] 괄호 변환 - 자바스크립트  (0) 2021.06.18
[프로그래머스] 게임 맵 최단거리 - 자바스크립트  (0) 2021.06.18
[프로그래머스] 땅따먹기 - 자바스크립트  (0) 2021.06.18
[프로그래머스] 크레인 인형뽑기 게임 - 자바스크립트  (0) 2021.04.19
[프로그래머스] 위장 - 자바스크립트  (0) 2021.04.18
    'DS & Algorithm/programmers' 카테고리의 다른 글
    • [프로그래머스] 게임 맵 최단거리 - 자바스크립트
    • [프로그래머스] 땅따먹기 - 자바스크립트
    • [프로그래머스] 크레인 인형뽑기 게임 - 자바스크립트
    • [프로그래머스] 위장 - 자바스크립트
    jiho_bae
    jiho_bae
    하루에 한 걸음씩

    티스토리툴바