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

[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차 풀이: 포인터