[Algorithm] 택배 배달과 수거하기 (Programmers / JavaScript)

문제 설명

 

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i 만큼 떨어져 있습니다. (1 <= i <= j <= n)

트럭에는 재활용 택배 상자를 최대 cap개를 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

 

 

 

 

---

 

 

 

제한사항

 

 

 

 

---

 

 

 

입출력 예

 

 

 

 

---

 

 

 

문제 풀이

 

function solution(cap, n, deliveries, pickups) {
  let answer = 0;
 
  const deliveriesStack = [];
  const pickupsStack = [];
 
  for (let i = 0; i < deliveries.length; ++i) {
    const delivery = deliveries[i];
    const pickup = pickups[i];
    const location = i + 1;
 
    if (delivery !== 0) {
      deliveriesStack.push([location, delivery]);
    }
 
    if (pickup !== 0) {
      pickupsStack.push([location, pickup]);
    }
  }
 
  while (deliveriesStack.length > 0 || pickupsStack.length > 0) {
    let maxDistance = 0;
    let truckDeliveryCapCount = 0;
    let truckPickupCapCount = 0;
 
    while (deliveriesStack.length > 0 && truckDeliveryCapCount < cap) {
      const [deliveryLocation, deliveryCount] =
        deliveriesStack[deliveriesStack.length - 1];
 
      const availableCapacity = cap - truckDeliveryCapCount;
      if (deliveryCount <= availableCapacity) {
        truckDeliveryCapCount += deliveryCount;
        deliveriesStack.pop();
      } else {
        truckDeliveryCapCount += availableCapacity;
        deliveriesStack[deliveriesStack.length - 1][1] -= availableCapacity;
      }
 
      maxDistance = Math.max(maxDistance, deliveryLocation);
    }
 
    while (pickupsStack.length > 0 && truckPickupCapCount < cap) {
      const [pickupLocation, pickupCount] =
        pickupsStack[pickupsStack.length - 1];
 
      const availableCapacity = cap - truckPickupCapCount;
      if (pickupCount <= availableCapacity) {
        truckPickupCapCount += pickupCount;
        pickupsStack.pop();
      } else {
        truckPickupCapCount += availableCapacity;
        pickupsStack[pickupsStack.length - 1][1] -= availableCapacity;
      }
 
      maxDistance = Math.max(maxDistance, pickupLocation);
    }
 
    answer += maxDistance;
  }
 
  return answer * 2;
}