# [스택/큐][lv3] 다리를 지나는 트럭 - 자바스크립트 js

# 프로그래머스 문제

https://programmers.co.kr/learn/courses/30/lessons/42583 (opens new window)

# 시도 1.

이 문제를 잠깐 봤다가 며칠 후 다시 보고 그래서.. 이 코드가 맨 처음 제출 했던 코드인건 기억이 나지만.. 뭔가 정리하지 않고 무작정 코딩했다가 예외사항 발견 → 로직이 잘못됐다는 걸 깨닫고 엎었어야 했는데 일단 그 예외사항 수정에 급급함의 패턴으로 막 적었던 것 같다. 로직을 생각하지 않고 테스트케이스에만 맞춤.

지금보니 보이는 문제점들

while(truck_weights.length !== 0) : 마지막 트럭은 다리를 건너지 못한 채 종료됨
totalWeights : 굳이 reduce를 쓰지 않고 crossTrucks 배열에 push 할때 단순 덧셈하면 됨
그외 하단 코드들은 처음에는 저렇게 지저분하지 않았는데 예외를 해결하기위해 막 코딩한 냄새가 난다..

function solution(bridge_length, weight, truck_weights) {
  var answer = 0;
  var crossTrucks = []; // 다리를 건너는 중인 트럭 배열

  while (truck_weights.length !== 0) {
    var totalWeights = crossTrucks.reduce((acc, cur) => (acc += cur[0]), 0);
    if (truck_weights[0]) totalWeights += truck_weights[0];

    if (crossTrucks.length < bridge_length && totalWeights <= weight) {
      // 새로 다리 건너는 트럭
      crossTrucks.push([truck_weights.shift(), 1]);
    } else {
      crossTrucks.map((v, i) => v[1]++);
    }
    answer++;

    // 길이가 다 찼거나, 다음 트럭이 오면 무게가 초과되는 경우
    if (crossTrucks.length == bridge_length || totalWeights > weight) {
      while (crossTrucks[0][1] < bridge_length) {
        crossTrucks.map((v, i) => v[1]++);
        answer++;
      }
      crossTrucks.shift();
    } else {
      crossTrucks.map((v, i) => v[1]++);
    }
  }

  return answer;
}

# 시도2.

시도1을 해보고 이틀 후 시간이 나서 다시 봤다. 이전번엔 문제자체를 제대로 이해하지 못했다는 걸 깨달음.. 예제 돌아가는 것 좀 자세히 볼 걸..

아무튼 시도1 코드는 싹 지우고 다시 처음부터 접근함. 문제를 보며 수도코드까진 아니더라도 텍스트로 어떻게 짜야 할지 정리를 해봤다.

1. 다리를 건너는 트럭의 개수 < bridge_length && 다음 트럭 + 현재 다리건너는트럭 총 무게 <= truck_weights 면 다리를 건너는 트럭배열에 트럭 추가
2. 그렇지 않으면 1초 추가, 다리 건너는 트럭들도 1 추가
3. 다 건넜다면 빠지기

테스트 코드도 하나 새로 만들어보고, 코딩을 했다. 그리고 역시나 오류(caption1, caption2)가 났다. 하단 코드는 오류를 모두 수정한 코드입니다.

crossTrucks

[ [트럭무게, 건넌length]... ] 2차원배열.

건넌 lenght가 다리 길이보다 길면 트럭은 다리를 건넌 것이다.(같을때는 다 건넌 것 아님!!)

추가로 만들어본 테스트 코드

bridge_length 3
weight 10
truck_weights [3, 5, 2, 4]
Return 8

초 트럭 배열
1  3
2  3 5
3  3 5 2
4    5 2
5      2 4
6        4
7        4
8

function solution(bridge_length, weight, truck_weights) {
  var answer = 0;
  let crossTrucks = []; // 다리를 건너는 중인 트럭 배열
  let crossTrucksWeights = 0; // 다리 건너는 중인 트럭 총 무게

  // ---- caption1 start
  var newTruck = truck_weights.shift();
  crossTrucks.push([newTruck, 0]);
  crossTrucksWeights += newTruck;
  // ---- caption1 end

  while (crossTrucks.length !== 0) {
    answer++;
    crossTrucks.map((v, i) => v[1]++);

    // 첫번째 트럭이 건넌lenght가 bridge_length보다 크다면 삭제.
    if (crossTrucks[0][1] > bridge_length) {
      crossTrucksWeights -= crossTrucks.shift()[0];
    }

    // 다리를 건너는 트럭의 개수 < bridge_length이고,
    // 다음 트럭 + 현재 다리건너는트럭의 총 무게가 weight보다 작거나 같다면
    // 다음 트럭이 올라올 수 있다.
    if (crossTrucks.length < bridge_length && truck_weights[0] + crossTrucksWeights <= weight) {
      var newTruck = truck_weights.shift();
      // ---- caption2 start
      crossTrucks.push([newTruck, 1]);
      // ---- caption2 start
      crossTrucksWeights += newTruck;
    }
  }

  return answer;
}

caption1

처음 코딩했을 땐 이부분이 아예 없었다. 하지만 if( crossTrucks[0][1] > bridge_length ) 이 부분에서 이차원배열이라 '1'을 찾을 수 없다는 오류도 있었다.

또한 while문 조건이 처음에는 truck_weights.length !== 0 이랬으나, 이렇게 간다면 마지막 트럭이 다리를 건너는 중이면 남은 트럭이 없어 while문이 종료되므로 crossTrucks.length !== 0 로 바꿨다.

이 두가지 문제를 해결하기 위해 while문 밖에서 하나를 밀고 시작했다.
caption2

crossTrucks.push([newTruck, 0]); 이렇게 코딩했었다. 지금 생각해보면 왜그랬는지 모르겠지만, 트럭이 다리를 건너는 배열에 들어가면 일단 다리를 건너는 중 이므로 해당 트럭의 건넌lenght를 1로 해주어야 한다.

# 결과

사실 효율성을 고려하지 않?못해서 한두개 정도는 시간초과가 날 줄 알았는데 의외로 통과했다...

채점을 시작합니다.
정확성  테스트
테스트 1 〉	통과 (0.73ms, 30.2MB)
테스트 2 〉	통과 (14.61ms, 33.9MB)
테스트 3 〉	통과 (0.20ms, 29.9MB)
테스트 4 〉	통과 (11.77ms, 34.2MB)
테스트 5 〉	통과 (29.42ms, 34.2MB)
테스트 6 〉	통과 (17.55ms, 34.1MB)
테스트 7 〉	통과 (0.78ms, 30MB)
테스트 8 〉	통과 (0.34ms, 29.9MB)
테스트 9 〉	통과 (5.47ms, 32.3MB)
테스트 10 〉	통과 (0.35ms, 29.9MB)
테스트 11 〉	통과 (0.13ms, 30MB)
테스트 12 〉	통과 (0.27ms, 29.8MB)
테스트 13 〉	통과 (1.61ms, 29.8MB)
테스트 14 〉	통과 (0.11ms, 30MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

# 다른 사람 답변 통해 배워보기

console.log를 찍어보면서 했을 때, 테스트케이스2(다리길이100,무게100,트럭리스트[10]리턴값101) 의 로그를 보면서 아.. 내코드는 다리 길이가 길면 그만큼 loop를 돌아야 하는 구나 생각하긴했다. 그리고 역시나 다른 분들의 답변을 보니 쓸데없는 loop를 방지 하도록 코딩을 했음

// 3. 다음 트럭이 못올라오는 상황이면 얼른 큐의
      //    첫번째 트럭이 빠지도록 그 시간으로 점프한다.
      //    참고: if 밖에서 1 더하기 때문에 -1 해줌
      if (qu[0]) time = qu[0][1] - 1;

그래서 나도 내 코드를 수정해봄.

else-if 문이 추가 되었는데, 첫번째 트럭이 나갈 준비가 되지 않았을 때 ,즉 answer++ 수행 후 crossTrucks[0][1] > bridge_length 조건이 만족하지 않을 때 elseif 문 안으로 들어가야 하므로 crossTrucks[0][1] < bridge_length 조건을 추가했다.

function solution(bridge_length, weight, truck_weights) {
    var answer = 0;
    let crossTrucks = []; // 다리를 건너는 중인 트럭 배열
    let crossTrucksWeights = 0; // 다리 건너는 중인 트럭 총 무게

    var newTruck = truck_weights.shift();
    crossTrucks.push([newTruck, 0]);
    crossTrucksWeights += newTruck;

    while(crossTrucks.length !== 0){
        answer++;
        crossTrucks.map((v,i) => v[1]++);

        if( crossTrucks[0][1] > bridge_length ){
            crossTrucksWeights -= crossTrucks.shift()[0];
        }

        if( crossTrucks.length < bridge_length && truck_weights[0] + crossTrucksWeights <= weight ){
            var newTruck = truck_weights.shift();
            crossTrucks.push([newTruck, 1]);
            crossTrucksWeights += newTruck;

        } else if(crossTrucks.length !== 0 && crossTrucks[0][1] < bridge_length){
            var length = bridge_length - crossTrucks[0][1];
            answer += length;
            crossTrucks.map((v,i) => v[1]+=length);
        }

    }

    return answer;

}

채점을 시작합니다.
정확성  테스트
테스트 1 〉	통과 (0.15ms, 30.1MB)
테스트 2 〉	통과 (0.16ms, 30MB)
테스트 3 〉	통과 (0.12ms, 30MB)
테스트 4 〉	통과 (0.96ms, 30MB)
테스트 5 〉	통과 (2.52ms, 30MB)
테스트 6 〉	통과 (1.25ms, 30MB)
테스트 7 〉	통과 (0.15ms, 30.1MB)
테스트 8 〉	통과 (0.17ms, 30MB)
테스트 9 〉	통과 (0.69ms, 30MB)
테스트 10 〉	통과 (0.17ms, 30MB)
테스트 11 〉	통과 (0.16ms, 30MB)
테스트 12 〉	통과 (0.25ms, 30MB)
테스트 13 〉	통과 (0.26ms, 30.1MB)
테스트 14 〉	통과 (0.13ms, 30MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

눈에 띄게 시간이 줄었다! 굿

← [스택/큐][Lv2] 프린터 - 자바스크립트 js [힙][Lv3] 디스크 컨트롤러 - 자바스크립트 js →