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

<목차>

1. 문제
2. 접근 방법
3. 풀이 소스

 

[문제]

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

각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

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

 

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

배달 및 수거 과정

	집 #1	집 #2	집 #3	집 #4	집 #5	설명
남은 배달 / 수거	1 / 0	0 / 3	3 / 0	1 / 4	2 / 0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달 / 수거	1 / 0	0 / 3	3 / 0	0 / 4	0 / 0	물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달 / 수거	1 / 0	0 / 3	3 / 0	0 / 0	0 / 0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달 / 수거	0 / 0	0 / 3	0 / 0	0 / 0	0 / 0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달 / 수거	0 / 0	0 / 0	0 / 0	0 / 0	0 / 0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

---

[접근 방법]

Greedy 알고리즘

1. 배송지 / 수거지 중, 가장 멀리 있는 곳으로 이동 (편의를 위해 'T 지점' 이라고 표현)
2. 출발하며 cap 개 만큼 트럭에 싣고, T 지점으로 이동
3. T 지점까지 이동하며, 배송 물건 하차
   >> T 지점 까지 이동하며, 차에 실은 택배를 멀리 있는 곳 우선으로 배달
   >> 가장 멀리 있는 곳부터 배달한다고 이해하면 편함 (액션은 T 지점까지 배달하면서 이동 -> 가장 멀리있는 T 지점부터 수거해와야되기 때문)

<Example>
cap = 4 / deliveries = {1, 1, 2, 2, 1} / pickups = {0, 1, 2, 3, 0}
T 지점 확인
>> deliveries 에서 0이 아닌 마지막 집 = 집 #5
>> pickups 에서 0이 아닌 마지막 집 = 집 #4

*** T 지점 : 집 #5

[첫번째 사이클]
1) 트럭에 4개 싣고 출발
2) 집 #3에 1개 배달
3) 집 #4에 2개 배달
4) 집 #5에 1개 배달
5) 배달 완료 -> deliveries = {1, 1, 1, 0, 0}
6) 집 #4에서 3개 수거
7) 집 #3 에서 1개 수거
8) 수거 완료 -> pickups = {0, 1, 1, 0, 0}

* * * 반복 * * *

 

---

[풀이 소스]

public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        
    //Greedy
    //남은 갯수 / cap개 Min 싣고 출발 > 뒤에서부터 없애지만 제일 이동 거리는 제일 마지막 칸
    //배송 후, 가장 마지막 수거 상자부터 cap개 채워서 복귀

    long distance = 0;

    int dLast = deliveries.length - 1;
    int pLast = pickups.length - 1;

    int dSum = 0;
    int pSum = 0;

    while(true) {

        //가장 멀리있는 배송지 / 수거지 탐색
        dLast = findLastHomeIndex(deliveries, dLast);
        pLast = findLastHomeIndex(pickups, pLast);

        //모두 탐색 후 종료
        if(dLast == 0 && deliveries[dLast] == 0 && pLast == 0 && pickups[pLast] == 0) {
            break;
        }

        //거리 계산 (집은 1부터 시작하므로 +1)
        distance += (Math.max(dLast, pLast) + 1) * 2;

        dSum = 0;
        pSum = 0;

        //배송 진행
        while(dSum < cap && deliveries[dLast] > 0) {
            dSum += 1;
            deliveries[dLast] -= 1;

            if(deliveries[dLast] == 0) {
                dLast = findLastHomeIndex(deliveries, dLast);
            }
        }

        //수거 진행
        while(pSum < cap && pickups[pLast] > 0) {
            pSum += 1;
            pickups[pLast] -= 1;

            if(pickups[pLast] == 0) {
                pLast = findLastHomeIndex(pickups, pLast);
            }
        }
    }

    return distance;
}
	
//배송,수거 배열의 0이 아닌 마지막 인덱스 확인
public int findLastHomeIndex(int[] array, int lastIdx) {
    while(lastIdx > 0 && array[lastIdx] == 0) {lastIdx--;}
    return lastIdx;
}