[pro] 프로그래머스 level2 택배 배달과 수거하기 (Java) - 그리디

[문제]

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

프로그래머스

 

[풀이]

전혀 level2 같지 않은 문제...(◞‸◟；)

트럭 하나로 배달/수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동거리를 구해야 한다. 이동거리가 최소가 되기 위해서는 가장 멀리 있는 집부터 배달/수거를 완료해서 다시 그 집을 가지 않도록 만들어야 한다. 가장 멀리 있는 집에서 배달/수거를 했을 때 트럭의 용량이 남았다면 돌아오면서 다른 집의 배달/수거도 할 수 있을 것이다. 

따라서 중요한 점은, 가장 멀리 있는 집으로 이동할 때(-> 방향) 최대 용량만큼 배달하면서 이동이 가능하고, 다시 그 집에서 물류창고로 이동할 때(<- 방향) 택배 상자를 다 배달했기 때문에 트럭이 빈 상태라는 것이다. 그럼 다시 최대 용량만큼 수거가 가능해진다. 

최대용량만큼 배달이 가능하고, 최대용량만큼 수거가 가능하다는 점이 핵심이다!

 

예제 1을 해당 알고리즘으로 자세히 살펴보면 다음과 같다.

 

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

 

1. 집 5부터 이동해서 배달해야하는 택배와 수거해야 하는 택배를 차감한다. 또한 물류창고와 집 5 사이의 왕복 거리를 정답에 더해준다.-> d = -2, p = 0. answer = 10.

2. cap만큼 배달/수거가 가능하므로 cap을 더해준다. -> d = 2, p = 4. d가 2라는 것은 물류창고에서 집 5방향으로 이동하면서 2개만큼 더 배달할 택배를 싣고 갈 수 있다는 것이다. 마찬가지로 p가 4라는 것은 집 5에서 물류창고로 이동하면서 4개의 택배를 수거해갈 수 있다는 것이다. 둘 다 0 이상이므로 아직 트럭 용량의 여유가 있다는 것을 의미한다. 따라서 집 4로 이동한다.

3. 집 4에서 배달/수거해야 하는 택배를 차감한다. -> d = 1, p = 0. d가 1라는 것은 물류창고에서 집 4방향으로 이동하면서 1개만큼 더 배달할 택배를 싣고 갈 수 있다는 것이다. p = 0은 집 4에서 물류창고로 이동하면서 수거 가능한 용량이 꽉 찼다는 것이다. 하지만 둘다 0이상이므로 집 4에서 더 배달/수거해야 할 택배는 없다. 따라서 집 3으로 이동한다.

4. 집 3에서 배달/수거해야 하는 택배를 차감한다. -> d = -2, p = 0. d가 -2라는 것은 물류창고에서 집 3 방향으로 이동하면서 집 3에 배달 가능한 택배 용량이 초과되었다는 것이다. 이는 집 3을 다시 방문해야 함을 의미한다. 따라서 집 3을 다시 방문해줘야 하므로 while문 속 코드를 수행한다. (집 3에 다시 방문해서 배달/수거를 하고, 집 3까지의 왕복 거리를 정답에 더해줌) -> d = 2, p = 4, answer = 16. 집 3에 택배 남아있던 택배 2개를 배달하고도 배달할 택배 2개를 더 싣고 갈 수 있을 여유가 있으며, 물류창고로 돌아오는 중에 4개를 수거할 수 있다는 것을 의미한다.

5. 집 2에서 배달/수거해야 하는 택배를 차감한다. -> d = 2, p = 1.

6. 집 1에서 배달/수거해야 하는 택배를 차감한다. -> d = 1, p = 1.

7. 반복문이 끝났다. answer = 16.

 

리프레시 하려고 level2 문제 잡았다가 힌트를 봐도 이해가 안돼서 진짜 자괴감 max 됨...코드만 보면 level2가 맞아서 더 현타왔던 문제ㅎㅎ 카카오 진짜 너무하다...

 

[코드]

 

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        //트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 
        
        int d = 0;
        int p = 0;
        for(int i=n-1; i>=0; i--){
            d -= deliveries[i];
            p -= pickups[i];
            
            while(d < 0 || p < 0){
                d += cap;
                p += cap;
                answer += (i+1)*2;
            }
        }
        
        return answer;
    }
}