[프로그래머스] 택배 배달과 수거하기 풀이 및 코드 분석

문제 링크

---

1. 문제 분석

📌 문제 개요

택배 트럭이 여러 집을 방문하여 택배를 배달하고 빈 택배 상자를 수거해야 한다.
트럭은 최대 cap개의 택배만 실을 수 있으며, 모든 집을 방문한 뒤 물류창고로 돌아와야 한다.

 

🚩 목표:
모든 배달과 수거를 완료하는 데 필요한 최소 이동 거리를 계산하기.

📌 문제의 제약 조건

• 배달과 수거를 동시에 진행 가능.
• 한 번에 최대 cap개의 택배만 실을 수 있음.
• deliveries[i]: i+1번 집에 배달해야 하는 택배 수
• pickups[i]: i+1번 집에서 수거해야 하는 빈 택배 수
• n ≤ 100,000 이므로 O(N^2) 이상의 시간 복잡도는 비효율적.

---

2. 해결 방법

🔹 그리디 (Greedy) 알고리즘 활용

• 핵심 아이디어:
  • 가장 먼 집부터 배달 및 수거를 처리하면 불필요한 이동을 줄일 수 있음.
  • 트럭이 왕복해야 하므로 최대한 먼 거리에서 한 번에 처리하는 것이 효율적.

🔹 구체적인 진행 방식

1. 배달과 수거가 필요한 마지막 집(dIdx, pIdx)을 찾음
2. 가장 먼 집까지 이동(max(dIdx, pIdx))하고 왕복 거리(2배)를 추가
3. 트럭 용량(cap)만큼 배달과 수거를 진행
   • 트럭이 가득 차거나 모든 배달/수거가 끝날 때까지 반복
4. 위 과정을 모든 집이 처리될 때까지 반복하여 최소 이동 거리를 계산

---

3. 코드 구현 (Java)

class Solution {
  public static long solution(int cap, int n, int[] deliveries, int[] pickups) {
    long answer = 0;

    int dIdx = n - 1; // 배달이 필요한 마지막 집
    int pIdx = n - 1; // 수거가 필요한 마지막 집

    while (!(dIdx < 0 && pIdx < 0)) {

      // 배달이 필요한 마지막 집 찾기
      while (dIdx >= 0 && deliveries[dIdx] == 0) {
        dIdx--;
      }

      // 수거가 필요한 마지막 집 찾기
      while (pIdx >= 0 && pickups[pIdx] == 0) {
        pIdx--;
      }

      // 트럭이 이동해야 할 최대 거리
      int l = Math.max(dIdx, pIdx);
      answer += 2 * (l + 1);

      // 배달 처리
      int c = cap;
      while (c > 0 && dIdx >= 0) {
        if (deliveries[dIdx] >= c) {
          deliveries[dIdx] -= c;
          c = 0;
          if (deliveries[dIdx] == 0) dIdx--;
          break;
        }

        c -= deliveries[dIdx];
        deliveries[dIdx] = 0;
        dIdx--;
      }

      // 수거 처리
      c = cap;
      while (c > 0 && pIdx >= 0) {
        if (pickups[pIdx] >= c) {
          pickups[pIdx] -= c;
          c = 0;
          if (pickups[pIdx] == 0) pIdx--;
          break;
        }

        c -= pickups[pIdx];
        pickups[pIdx] = 0;
        pIdx--;
      }

    }

    return answer;
  }
}

---

4. 코드 분석

🔹 주요 알고리즘 및 로직

1. 가장 먼 배달/수거 지점을 찾음
   • 불필요한 왕복을 방지하기 위해 마지막 배달/수거 지점만 방문
2. while (dIdx >= 0 && deliveries[dIdx] == 0) dIdx--; while (pIdx >= 0 && pickups[pIdx] == 0) pIdx--;
3. 트럭이 이동해야 할 거리 계산
   • 배달과 수거를 함께 처리하기 위해 최대 거리(l)까지 이동
   • 왕복해야 하므로 2배(2 * (l + 1))를 더함
4. int l = Math.max(dIdx, pIdx); answer += 2 * (l + 1);
5. 트럭의 용량(cap) 내에서 배달과 수거 진행
   • 트럭에 남은 용량이 있을 때, 최대한 많은 택배 배달
   • 모든 배달이 완료되면 dIdx--를 통해 다음 집으로 이동

   c = cap;
   while (c > 0 && pIdx >= 0) {
       if (pickups[pIdx] >= c) {
           pickups[pIdx] -= c;
           c = 0;
           if (pickups[pIdx] == 0) pIdx--;
           break;
       }
   
       c -= pickups[pIdx];
       pickups[pIdx] = 0;
       pIdx--;
   }

   • 배달과 동일한 방식으로 수거 진행
6. int c = cap; while (c > 0 && dIdx >= 0) { if (deliveries[dIdx] >= c) { deliveries[dIdx] -= c; c = 0; if (deliveries[dIdx] == 0) dIdx--; break; } c -= deliveries[dIdx]; deliveries[dIdx] = 0; dIdx--; }

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. 배달과 수거를 한 번에 처리하는 방식 개선
   • 현재는 배달과 수거를 각각 반복하면서 cap을 조정하는 방식
   • 하지만 트럭에 남은 용량을 배달과 수거가 유동적으로 사용할 수 있도록 하면 왕복 횟수를 줄일 수 있음
2. PriorityQueue를 사용한 최적화
   • 현재는 deliveries와 pickups를 직접 순회하며 남은 물량을 확인
   • 우선순위 큐(PriorityQueue)를 사용하여 가장 먼 집을 빠르게 찾으면 성능을 더 개선할 수 있음

🚀 대체 가능한 방법

✅ 스택을 이용한 최적화

• 스택을 사용하여 남은 배달/수거 물량을 효율적으로 관리
• 더 빠르게 최적 배달 및 수거 경로 탐색 가능

import java.util.Stack;

class Solution {
  public static long solution(int cap, int n, int[] deliveries, int[] pickups) {
    long answer = 0;

    Stack<Integer> dStack = new Stack<>();
    Stack<Integer> pStack = new Stack<>();

    for (int i = 0; i < n; i++) {
      if (deliveries[i] > 0) dStack.push(i);
      if (pickups[i] > 0) pStack.push(i);
    }

    while (!dStack.isEmpty() || !pStack.isEmpty()) {
      int dMax = dStack.isEmpty() ? 0 : dStack.peek();
      int pMax = pStack.isEmpty() ? 0 : pStack.peek();
      int l = Math.max(dMax, pMax);

      answer += 2 * (l + 1);

      int c = cap;
      while (!dStack.isEmpty() && c > 0) {
        int idx = dStack.peek();
        if (deliveries[idx] > c) {
          deliveries[idx] -= c;
          break;
        }
        c -= deliveries[idx];
        dStack.pop();
      }

      c = cap;
      while (!pStack.isEmpty() && c > 0) {
        int idx = pStack.peek();
        if (pickups[idx] > c) {
          pickups[idx] -= c;
          break;
        }
        c -= pickups[idx];
        pStack.pop();
      }
    }

    return answer;
  }
}