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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/150369

문제 설명

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

제한사항

알고리즘: 구현

풀이

목표는 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리이다.
최소 이동 거리를 보장하기 위해서 거리가 먼 house를 최소한으로 방문해야 한다. 그러면 최소한으로 방문하기 위해서는 어떻게 해야 할까? 방법은 거리가 먼 house를 우선으로 배달해 주고, 우선으로 수거하면 된다. 예를 들면 1, 2, 3, 4의 하우스가 있다면, 4를 우선적으로 배달, 수거하고 충족이 되면 남은 상자는 그다음으로 먼 3번 하우스 (실제로는 4번으로 배달하러 갈 때 그 남은 상자를 3번에 배달한다고 생각하면 이해하기 쉽다.) 그리고 다시 트럭에 택배를 실어서 거리가 먼 house를 우선적으로 처리해 준다. 이런 식으로 반복해서 모든 배달과 수거를 마치면 최소 이동 거리를 보장할 수 있다.

소스 코드

import java.util.*;
class Node {
    int h, c;
    Node(int h, int c) {
        this.h = h;
        this.c = c;
    }
}
class Solution {
    static ArrayList < Node > d_list = new ArrayList < > ();
    static ArrayList < Node > p_list = new ArrayList < > ();
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        for (int i = 0; i < n; i++) {
            if (deliveries[i] != 0) d_list.add(new Node(i + 1, deliveries[i]));
            if (pickups[i] != 0) p_list.add(new Node(i + 1, pickups[i]));
        }
        while (d_list.size() != 0 || p_list.size() != 0) {
            int house = 0;
            if(d_list.size() == 0) house = p_list.get(p_list.size()-1).h;
            else if(p_list.size() == 0) house = d_list.get(d_list.size()-1).h;
            else house = Math.max(d_list.get(d_list.size()-1).h, p_list.get(p_list.size()-1).h);
            delivery_pickup(d_list, cap);
            delivery_pickup(p_list, cap);
            answer += house * 2;
        }
        return answer;
    }
    static void delivery_pickup(ArrayList < Node > list, int box) {
        while (box != 0 && list.size() != 0) {
            if (list.get(list.size() - 1).c > box) {
                list.get(list.size() - 1).c -= box;
                box = 0;
            } else {
                box -= list.get(list.size() - 1).c;
                list.remove(list.size() - 1);
            }
        }
    }
}