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

🎨 문제

프로그래머스

📘 풀이

이 문제는 그리디로 문제를 해결할 수 있습니다. 가장 멀리 있는 배달을 갔을 때 가장 멀리 있는 택배 상자를 수거하면 됩니다. 즉, 다음과 같은 전략으로 문제를 해결할 수 있습니다.

 

1. 배달 및 수거할 택배 상자가 남은 가장 먼 집부터 택배를 배달 및 수거합니다.

2. 트럭이 물류창고에서 출발해 가장 먼 집으로 이동할 때는 배달만 하고, 다시 물류창고로 돌아올 때는 수거만 합니다.

3. 트럭이 물류창고에서 출발할 때 항상 택배를 최대 개수만큼 배달하고, 물류창고로 돌아갈 때 최대 개수만큼 수거합니다.

 

스택을 활용하면 편하게 구현할 수 있습니다. 배달 및 수거할 택배 상자의 위치와 그 개수만큼 순서대로 스택에 넣습니다.

 

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

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

 

가장 멀리 떨어진 배달 및 수거해야 할 집을 구하고 한쪽 스택이 빌 때까지 뒤에서부터 cap 개수만큼 배달 및 수거를합니다. 이때 배달 및 수거를 한 거리는 왕복 거리이므로 가장 먼 집에서 곱하기 2를 해줍니다.

 

while (!dStack.isEmpty() && !pStack.isEmpty()) {
    int lastD = dStack.peek();
    int lastP = pStack.peek();

    for (int i = 0; i < cap; i++) {
        if (!dStack.isEmpty()) dStack.pop();
        if (!pStack.isEmpty()) pStack.pop();
    }

    answer += Math.max(lastD, lastP) * 2L;
}

 

마지막으로 남은 배달 혹은 수거를 합니다.

 

while (!dStack.isEmpty()) {
    int last = dStack.peek();

    for (int i = 0; i < cap; i++) {
        if (!dStack.isEmpty()) dStack.pop();
    }

    answer += last * 2L;
}

while (!pStack.isEmpty()) {
    int last = pStack.peek();

    for (int i = 0; i < cap; i++) {
        if (!pStack.isEmpty()) pStack.pop();
    }

    answer += last * 2L;
}

📗 코드

import java.util.Stack;

public class Solution {

    public 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++) {
            for (int j = 0; j < deliveries[i]; j++) {
                dStack.push(i + 1);
            }
            for (int j = 0; j < pickups[i]; j++) {
                pStack.push(i + 1);
            }
        }

        while (!dStack.isEmpty() && !pStack.isEmpty()) {
            int lastD = dStack.peek();
            int lastP = pStack.peek();

            for (int i = 0; i < cap; i++) {
                if (!dStack.isEmpty()) dStack.pop();
                if (!pStack.isEmpty()) pStack.pop();
            }

            answer += Math.max(lastD, lastP) * 2L;
        }

        while (!dStack.isEmpty()) {
            int last = dStack.peek();

            for (int i = 0; i < cap; i++) {
                if (!dStack.isEmpty()) dStack.pop();
            }

            answer += last * 2L;
        }

        while (!pStack.isEmpty()) {
            int last = pStack.peek();

            for (int i = 0; i < cap; i++) {
                if (!pStack.isEmpty()) pStack.pop();
            }

            answer += last * 2L;
        }

        return answer;
    }
}