프로그래머스 [공부 : 다리를 지나는 트럭]

다리를 지나는 트럭

 

내가 처음 푼 풀이

Logic
1.  다리위에 트럭들의 총무게가 다음 트럭도 감당할 수 있으면 트럭이 올라가고
2. 1의 조건에 만족하지 않으면 조건에 만족 할때까지 다음 트럭은 기다리고
3. 기다리는 트럭이 전부 다리위로 올라가면
4. 마지막 트럭이 올라간 시간 + 다리에서 내려가는데 걸리는 시간이 
    모든 트럭이 내려오는 시간

function solution(bridge_length, weight, truck_weights) {
  // 다리 위의 트럭 정보
  let onBridge_Arr = Array(bridge_length).fill(0);
  // 걸리는 시간
  let time = 0;
  let i = 0;

  // 트럭이 전부 지나갈때 까지 반복
  while (i < truck_weights.length) {
    onBridge_Arr.shift();
    if (sumArr(onBridge_Arr) + truck_weights[i] > weight) {
      onBridge_Arr.push(0);
    } else {
      onBridge_Arr.push(truck_weights[i]);
      i++;
    }
    time++;
  }
  // 마지막 트럭이 들어갔다면 다리의 기리만큼 시간이 더걸림
  return time + bridge_length;
}
// 함수안의 인자를 전부 더하는 함수
function sumArr(arr) {
  return arr.reduce((acc, cur) => {
    return acc + cur;
  }, 0);
}

아쉬운점 

 - 너무느림

 - 다음 트럭이 올라갈수 있는지 확인할때마다 모든 인자들을 순회함

 

정확성 테스트

테스트 1 〉 통과 (32.30ms, 31.9MB)

테스트 2 〉 통과 (1059.72ms, 32.3MB)

테스트 3 〉 통과 (0.09ms, 30.3MB)

테스트 4 〉 통과 (252.16ms, 32.2MB)

테스트 5 〉 통과 (2401.63ms, 33.7MB)

테스트 6 〉 통과 (664.46ms, 32.8MB)

테스트 7 〉 통과 (17.32ms, 31.8MB)

테스트 8 〉 통과 (0.69ms, 29.8MB)

테스트 9 〉 통과 (30.57ms, 31.8MB)

테스트 10 〉 통과 (0.80ms, 29.7MB)

테스트 11 〉 통과 (0.11ms, 29.7MB)

테스트 12 〉 통과 (0.51ms, 29.8MB)

테스트 13 〉 통과 (4.91ms, 31.7MB)

테스트 14 〉 통과 (0.08ms, 29.9MB)

 

내가 푼 풀이 최적화

//? optimize soluiton
// reduce함수를 안써서 함수한번 사용할때마다 배열안의 인자를 전부 확인하는 시간을 줄임

function solution(bridge_length, weight, truck_weights) {
  // 다리 위의 트럭 정보
  let onBridge_Arr = Array(bridge_length).fill(0);

  // 다리위의 트럭 총 무게
  let onBrigeWeight = 0;
  // 걸리는 시간
  let time = 0;
  let i = 0;

  // 트럭이 전부 지나갈때 까지 반복
  while (i < truck_weights.length) {
    // 다리위에서 나가는 트럭이 있으면 무게가 줄어듬
    onBrigeWeight -= onBridge_Arr.shift();
    if (onBrigeWeight + truck_weights[i] > weight) {
      onBridge_Arr.push(0);
    } else {
      // 트럭이 올라오면 무게가 증가
      onBridge_Arr.push(truck_weights[i]);
      onBrigeWeight += truck_weights[i];
      i++;
    }
    time++;
  }
  // 마지막 트럭이 들어갔다면 다리의 기리만큼 시간이 더걸림
  return time + bridge_length;
}

아쉬운점 

  - 전보다는  빨라졌으나 아직 조금 느린부분이 있음

정확성 테스트

테스트 1 〉 통과 (0.28ms, 30MB)

테스트 2 〉 통과 (29.01ms, 32.8MB)

테스트 3 〉 통과 (0.05ms, 30.1MB)

테스트 4 〉 통과 (4.80ms, 32.8MB)

테스트 5 〉 통과 (26.49ms, 34.8MB)

테스트 6 〉 통과 (9.24ms, 33.6MB)

테스트 7 〉 통과 (0.34ms, 30.1MB)

테스트 8 〉 통과 (0.10ms, 30.1MB)

테스트 9 〉 통과 (3.13ms, 32.9MB)

테스트 10 〉 통과 (0.18ms, 30.2MB)

테스트 11 〉 통과 (0.06ms, 30MB)

테스트 12 〉 통과 (0.13ms, 30MB)

테스트 13 〉 통과 (0.37ms, 30.1MB)

테스트 14 〉 통과 (0.05ms, 30.2MB)

 

다른사람이 푼 풀이 1

// 다른사람 풀이1
function solution(bridge_length, weight, truck_weights) {
  // '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].
  let time = 0,
    qu = [[0, 0]],
    weightOnBridge = 0;

  // 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복
  while (qu.length > 0 || truck_weights.length > 0) {
    // 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면 내보내주고,
    //    다리 위 트럭 무게 합에서 빼준다.
    if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];

    if (weightOnBridge + truck_weights[0] <= weight) {
      // 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면
      //    다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
      weightOnBridge += truck_weights[0];
      qu.push([truck_weights.shift(), time + bridge_length]);
    } else {
      // 3. 다음 트럭이 못올라오는 상황이면 얼른 큐의
      //    첫번째 트럭이 빠지도록 그 시간으로 점프한다.
      //    참고: if 밖에서 1 더하기 때문에 -1 해줌
      if (qu[0]) time = qu[0][1] - 1;
    }
    // 시간 업데이트 해준다.
    time++;
  }
  return time;
}

소감

 - 트럭이 올라갈때 나가는 시간도 인자로 주어서 나가는 시간을 계산할 필요가 없어짐

 - 조금 더 최적화 할수 있을것 같음

정확성 테스트

테스트 1 〉 통과 (0.07ms, 30.3MB)

테스트 2 〉 통과 (0.11ms, 30.2MB)

테스트 3 〉 통과 (0.12ms, 29.8MB)

테스트 4 〉 통과 (0.17ms, 30.2MB)

테스트 5 〉 통과 (0.54ms, 30.1MB)

테스트 6 〉 통과 (0.39ms, 30MB)

테스트 7 〉 통과 (0.07ms, 30.2MB)

테스트 8 〉 통과 (0.09ms, 29.9MB)

테스트 9 〉 통과 (0.23ms, 30.2MB)

테스트 10 〉 통과 (0.08ms, 30.1MB)

테스트 11 〉 통과 (0.14ms, 30.1MB)

테스트 12 〉 통과 (0.11ms, 30.2MB)

테스트 13 〉 통과 (0.12ms, 30.1MB)

테스트 14 〉 통과 (0.07ms, 30.1MB)

 

다른사람 풀이1 최적화

// 다른사람 풀이1 optimize
function solution(bridge_length, weight, truck_weights) {
  // '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].
  let time = 0,
    qu = [[0, 0]],
    weightOnBridge = 0;

  // 대기 트럭이 없을 때 까지 다음 루프 반복
  while (truck_weights.length > 0) {
    // 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면
    //    내보내주고,다리 위 트럭 무게 합에서 빼준다.
    if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];

    if (weightOnBridge + truck_weights[0] <= weight) {
      // 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면
      //    다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
      weightOnBridge += truck_weights[0];
      qu.push([truck_weights.shift(), time + bridge_length]);
      // 시간 업데이트 해준다.
      time++;
    } else if (qu[0]) time = qu[0][1];
    // 3. 2의 조건에 해당하지 않고 다음 트럭이 존재한다면
    //    큐의 첫번째 트럭이 빠지도록 그 시간으로 점프한다.
  }
  // 4. 마지막 트럭이 올라갔다면
  //    그 마지막 트럭이 나가는 시간은
  //    올라간 시간 + 다리의 길이
  return time + bridge_length;
}

소감

 - 조금 줄여서 큰 차이는 없음

정확성 테스트

테스트 1 〉 통과 (0.10ms, 30MB)

테스트 2 〉 통과 (0.08ms, 29.8MB)

테스트 3 〉 통과 (0.10ms, 30.3MB)

테스트 4 〉 통과 (0.16ms, 30MB)

테스트 5 〉 통과 (0.34ms, 30MB)

테스트 6 〉 통과 (0.23ms, 30.1MB)

테스트 7 〉 통과 (0.07ms, 29.9MB)

테스트 8 〉 통과 (0.11ms, 30MB)

테스트 9 〉 통과 (0.24ms, 30MB)

테스트 10 〉 통과 (0.08ms, 30.1MB)

테스트 11 〉 통과 (0.09ms, 30.1MB)

테스트 12 〉 통과 (0.12ms, 30.2MB)

테스트 13 〉 통과 (0.12ms, 30.2MB)

테스트 14 〉 통과 (0.09ms, 29.8MB)

 

소감

 - 확실히 다른사람들의 코드를 보고 공부를 하니 내가 보지 못하였던 부분을 볼 수 있어서 좋았다.

 - 어렴풋이 시간을 빨리 넘기면 좋겠다라고 생각은 하였는데 어떻게 구현할지 고민하였으나
    내가 생각한 부분에 더하여 좀더 깔끔한 코드를 볼수 있어서 좋았다.

 

++ reference

https://programmers.co.kr/learn/courses/30/lessons/42583

github.com/