[프로그래머스] 택배 배달과 수거하기

https://school.programmers.co.kr/learn/courses/30/lessons/150369

 

 

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

 

 

 

---

문제요점

• n개 집, 최대 cap개 실을수 있다
• deliveries 집마다 배달해야할 상자 갯수, pickups 수거해야할 상자 갯수
• 최소이동거리를 구해라

 

생각

• 창고에서 가장 먼 집까지 이동하는 길 중간에 다른 집을 방문해도 됨
• 가장 먼 집의 배달, 수거부터 처리한다
• nlogn
• 실수: 배열의 마지막 원소가 항상 첫번째로 방문해야하는 집이라고 생각했다

 

• 첫번째로 방문해야하는 가장 먼 집을 찾는다
• 그 거리*2를 answer에 추가한다.
• 한번 창고에서 그 집까지 갔다가 돌아오는 길에서 배열의 오른쪽에서 왼쪽 순으로 cap만큼의 배달과 수거를 한다.
  • 현재 집의 배달/수거를 완료할 수 있으면 현재 집은 pop하여 더 이상 방문해야할 집에서 제외하고, 다음 집에서 남은 cap만큼을 배달/수거한다
  • 현재 집에서 배달/수거를 완료 할 수 없으면 현재 집에서 cap만큼의 배달/수거를 하고 창고로 돌아온다.

 

 

function solution(cap, n, deliveries, pickups) {
  var answer = 0;
  // 가장 먼 곳부터 방문하는데 방문할 필요가 없는 곳은 제외한다.
  while (deliveries[deliveries.length - 1] === 0) {
    deliveries.pop();
  }
  while (pickups[pickups.length - 1] === 0) {
    pickups.pop();
  }

  while (deliveries.length || pickups.length) {
    let amountCanTake = cap;
    answer += Math.max(deliveries.length, pickups.length) * 2; // 배달,수거를 해야하는 최대거리*2를 더한다.
    // 배달
    while (deliveries.length && amountCanTake) {
      // 가장 먼 집에 배달해야하는 양
      const mostFarDeliver = deliveries[deliveries.length - 1];
      // 현재 집에 배달을 완료할 수 있는 경우 다음집으로 배달을 계속한다.
      if (mostFarDeliver <= amountCanTake) {
        amountCanTake -= mostFarDeliver;
        deliveries.pop();
      }
      // 배달을 완료할 수 없으면 할 수 있을만큼만 배달하고 수거한다.
      else {
        deliveries[deliveries.length - 1] -= amountCanTake;
        amountCanTake = 0;
      }
    }
    // 배달을 안 해도 되는 집은 건너뛴다
    while (deliveries[deliveries.length - 1] === 0) {
      deliveries.pop();
    }
    amountCanTake = cap;
    // 수거
    while (pickups.length && amountCanTake) {
      const mostFarPickup = pickups[pickups.length - 1];
      if (mostFarPickup <= amountCanTake) {
        amountCanTake -= mostFarPickup;
        pickups.pop();
      } else {
        pickups[pickups.length - 1] -= amountCanTake;
        amountCanTake = 0;
      }
    }
    // 수거를 안 해도 되는 집은 건너뛴다
    while (pickups[pickups.length - 1] === 0) {
      pickups.pop();
    }
  }
  return answer;
}