[알고리즘 TIL] 택배 배달과 수거하기

문제

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

프로그래머스

프로그래머스 LV2 : 시뮬레이션

설명

이 문제는 LV2 문제로, 특별한 알고리즘을 요하는 문제는 아니지만, 쓸데없는 연산과 변수가 선언되면 실패하는 까다로운 문제였다. 

트럭 하나로 배달/수거를 마치고 물류 창고까지 돌아올 수 있는 최소 이동 거리를 구해야한다. 이동 거리가 최소가 되기 위해서는 가장 멀ㄹ리 있는 집부터 배달/수거를 완료해서 다시 그 집을 가지 않도록 만들었다. 

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int lastDeliveryCount = 0;
        int lastPickupCount = 0;

        //현재 남은 배달 갯수와 수거 갯수 저장
        for (int i = 0; i < n; i++) {
            lastDeliveryCount += deliveries[i];
            lastPickupCount += pickups[i];
        }

        while (lastDeliveryCount != 0 || lastPickupCount != 0) {
            //물류창고에서 cap과 낭믄 배달 갯수 중 더 작은 갯수만큼 챙김
            int lastCap = Math.min(cap, lastDeliveryCount);
            //먼 곳부터 배달
            int farthestDeliveryNum = 0;
            for (int i = n - 1; i >= 0; i--) {
                if (deliveries[i] > 0) {
                    if (farthestDeliveryNum == 0) farthestDeliveryNum = i+1;
                    //배달할 수 있는 마지막집인 경우
                    if (lastCap <= deliveries[i]) {
                        deliveries[i] -= lastCap;
                        lastDeliveryCount -= lastCap;
                        lastCap = 0;
                        break;
                    }//아직 택배 상자가 남은 경우
                    else {
                        lastCap -= deliveries[i];
                        lastDeliveryCount -= deliveries[i];
                        deliveries[i] = 0;
                    }
                }
            }
            //택배에 남은 공간
            int lastSpace = cap;
            //먼 곳부터 수거
            int farthestPickupNum = 0;
            for (int i = n - 1; i >= 0; i--) {
                if (pickups[i] > 0) {
                    if (farthestPickupNum == -0) farthestPickupNum = i+1;
                    //수거할 수 있는 마지막집인 경우
                    if (lastSpace <= pickups[i]) {
                        pickups[i] -= lastSpace;
                        lastPickupCount -= lastSpace;
                        lastSpace = 0;
                        break;
                    }//아직 트럭에 공간이 남은 경우
                    else {
                        lastSpace -= pickups[i];
                        lastPickupCount -= pickups[i];
                        pickups[i] = 0;
                    }
                }
            }
            //배달과 수거 중 더 멀리 간 곳을 결과에 더함
            answer += 2L * (Math.max(farthestDeliveryNum, farthestPickupNum));
        }
        return answer;
    }
}

기본적인 로직은 맞았지만, 테스트 20개 중 2개가 시간 초과로 실패했다. 배달과 수거를 진행할 때, 서로 다른 반복문에서 진행해서 그런가..? 해서 같은 루프에서 배달과 수거를 동시에 진행하는 방향으로 수정하였다.

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int lastDeliveryCount = 0;
        int lastPickupCount = 0;

        //현재 남은 배달 갯수와 수거 갯수 저장
        for (int i = 0; i < n; i++) {
            lastDeliveryCount += deliveries[i];
            lastPickupCount += pickups[i];
        }

        //배달 또는 수거할 집이 하나라도 남았으면 반복
        while (lastDeliveryCount > 0 || lastPickupCount > 0) {
            //물류창고에서 cap과 남은 배달 갯수 중 더 작은 갯수만큼 챙김
            int lastCap = Math.min(cap, lastDeliveryCount);
            //택배에 남은 공간
            int lastSpace = cap;
            //먼 곳부터 배달
            int farthestHouse = 0;
            //배달과 수거를 동시에 진행
            for (int i = n - 1; i >= 0; i--) {
                if (deliveries[i] > 0 || pickups[i] > 0) {
                    //배달 또는 수거를 진행할 제일 먼 집 위치 저장
                    if (farthestHouse == 0) farthestHouse = i + 1;
                    //배달 처리
                    if (deliveries[i] > 0) {
                        int deliverAmount = Math.min(lastCap, deliveries[i]);
                        deliveries[i] -= deliverAmount;
                        lastDeliveryCount -= deliverAmount;
                        lastCap -= deliverAmount;
                    }
                    //수거 처리
                    if (pickups[i] > 0) {
                        int pickupAmount = Math.min(lastSpace, pickups[i]);
                        pickups[i] -= pickupAmount;
                        lastPickupCount -= pickupAmount;
                        lastSpace -= pickupAmount;
                    }
                }
                if (lastCap == 0 && lastSpace == 0) break;
            }
            answer += 2L * farthestHouse;
        }
        return answer;
    }​

코드는 간결해졌지만, 시간 복잡도는 해결되지 않았다.

택배와 수거를 한 바퀴 진행하고 나면, 다시 택배와 수거를 진행하는 코드(while과 for문, 이중반복문)이므로, O(N^2)의 시간복잡도이다. 

 

다른 블로그의 코드를 참고하니, 단 한 바퀴만으로, 즉 O(N)으로 답을 구해냈다.

• 가장 멀리 떨어진 집부터 방문한다.
• 해당 집에 배달/수거할 박스가 없으면 그냥 패스한다.(continue)
• 배달/수거할 박스가 있으면 해당 집을 몇 번 왔다갔다해야하는지 구해서 이동 거리에 반영해준다.
• 이후, 배달할 수 있는 택배, 혹은 수거할 수 있는 공간이 남았으면 정보를 기록해준다. (남았으면 이 전 집에서 되돌아가는 길에 처리할 수 있기 때문)
• 남은 배달 혹은 수거 갯수를 고려하여 반복한다.

어떻게 이런 생각을 하지.. 더 열심히 해야겠다...

구현

public class Q_택배배달과수거하기_시뮬레이션 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int cap = 4;
        int n = 5;
        int[] deliveries = new int[]{1, 0, 3, 1, 2};
        int[] pickups = new int[]{0, 3, 0, 4, 0};
        long answer = solution.solution(cap, n, deliveries, pickups);
        System.out.println(answer);
    }

}

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

        for (int i = n - 1; i >= 0; i--) {
            //더 먼 집을 왔다갔다하며 처리한 집이여도, 처리한 갯수는 delivery와 pickup 변수에 갱신해주어야함
            //따라서 배달, 수거할 게 없는 집만 패스
            if (deliveries[i]==0 && pickups[i]==0) continue;
            //해당 집을 몇 번 왔다갔다해야하는지 구함
            int count = 0;
            while (delivery < deliveries[i] || pickup < pickups[i]) {
                count++;
                //왔다갔다하는 과정에서 만약 배달만 하는 경우에는 다른 집을 수거할 수도, 수거만 하는 경우에는 다른 집을 배달할 수 있음
                //따라서 수용 가능한 공간만큼 더하는 것임
                delivery += cap;
                pickup += cap;
            }
            //아래 계산 후 남은 값은 이미 오며가며 추가적으로 처리한 배달, 수거 갯수이므로 다음 집에 영향을 줌
            delivery -= deliveries[i];
            pickup -= pickups[i];
            answer += (long) (i+1) * count * 2;
        }
        return answer;
    }
}