[그리디] 택배배달과 수거하기

[ericagong]

⭐ 성찰

1. 최소거리 키워드가 나오면 그리디 / 최단거리 알고리즘 을 떠올리기
2. 굳이 Array.prototype.pop(), Array.prototype.shift() 등의 연산이 필요치 않고 포인터로만 처리할 수 있는지 고민해보기!

❓ 문제 상황

택배배달과 수거하기�

👨‍💻 문제 해결

✅ 1차 풀이: 스택을 이용한 그리디

• solution: 매번 트럭의 capacity 내에서 최대한 많은 양을 배달하고, 최대한 많은 양을 수거해오도록 처리
• 그리디 정당성: 배달을 할 때, 최대한 많이 가져가서 가져간 모든 택배를 배달함. 수거시에는 항상 capa에 가깝도록 최대한 가져오는 행위가 최적의 결과를 보장함.
  ㄴ ⭐ 이 때, 한 번 트럭 이동 거리 = 수거/배달 중 길이가 긴 거리 * 2

1. 우선, 정확한 길이를 알기위해 배달/수거 배열의 맨 뒤의 0을 없앰 처리해줌.
2. 배달/수거 배열의 맨 뒤부터 최대한 capacity만큼 택배 배달/수거 처리함.

function remove_zeros(arr) {
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] !== 0) break;
    else arr.pop();
  }
}

function move_truck(arr, cap) {
  let space = cap;
  while (arr.length > 0) {
    const curr = arr.pop();
    if (curr <= space) {
      space -= curr;
    } else {
      arr.push(curr - space);
      space = 0;
      break;
    }
  }
}

function solution(cap, n, deliveries, pickups) {
  remove_zeros(deliveries);
  remove_zeros(pickups);

  let distance = 0;
  while (deliveries.length > 0 || pickups.length > 0) {
    const d = Math.max(deliveries.length, pickups.length);
    distance += 2 * d;

    move_truck(deliveries, cap);
    move_truck(pickups, cap);
  }

  return distance;
}

✅ 2차 풀이: 포인터