[프로그래머스] 2023 KAKAO BLIND RECRUITMENT - 택배 배달과 수거하기 (Java)

 

프로그래머스

 

풀이

핵심은 트럭 하나로 모든 배달과 수거를 마치고 돌아오는 최소 이동 거리를 구하는 것

 

트럭이 최소 이동 거리로 움직이려면 최대한 멀리 떨어진 집의 배달과 수거를 먼저 완료시켜, 멀리 올 일이 없게 만들어야 한다.

- 주어진 배열을 뒤에서부터 찾도록 For문을 거꾸로 돌린다.

- 먼 집부터 방문 시, 해당 집에 배달/수거할 박스가 없다면 다음으로 넘어가도 좋다. 

 

트럭의 cap에 따라 한 집에 배달/수거 양을 한 번만에 수행할 수 없을 수도 있고, 오히려 트럭에 공간이 남을 수도 있다.

- 여러 번 왔다갔다 해야하는 경우 반복한 횟수만큼 이동 거리에 반영해줘야 하고,

- 공간이 남은 경우는 다른 집의 배달/수거 분을 같이 싣고 올 수 있도록 정보를 기록해줘야 한다.

 

코드

public class Solution {

    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliver = 0;
        int pickup = 0;

        for (int i = n - 1; i >= 0; i--) {
            // i번째 집에 배달/수거 박스가 없으면 방문하지 않아도 됨
            if (deliveries[i] == 0 && pickups[i] == 0) {
                continue;
            }

            // 같은 집을 몇번 왔다갔다해야하는지 횟수를 구함
            int count = 0;
            while (deliver < deliveries[i] || pickup < pickups[i]) {
                count++;
                deliver += cap;
                pickup += cap;
            }
            // 아래 계산 후 deliver, pickup에 남아있는 값은 같은 집을 몇번 오가는 중에 트럭에 남은 공간을 의미
            // 다음 집 횟수 구하는데 이용 됨
            deliver -= deliveries[i];
            pickup -= pickups[i];
            answer += (long) (i + 1) * count * 2;
        }

        return answer;
    }
}

 

도움받은 링크

[프로그래머스] 택배 배달과 수거하기 - 23 카카오 채용 (Java)

 

(문제를 처음 접하고 배달/수거 배열마다 Stack 혹은 pointer를 두어 해결하려고 했으나 구현이 너무 복잡해진 탓에 엣지 케이스들이 발생했다. 깔끔한 코드, 효율적인 코드를 떠나서 생각하는 것도 구현이 제대로 안되는 걸 보고 경각심을 조금은 느끼게 만들었던 문제였다)