[c#] 2023 KAKAO BLIND RECRUITMENT - 택배 배달과 수거하기

1. 효율을 따지지 않고 문제를 풀었을 경우 

- 물류창고에서 갈 땐 배달, 복귀할 땐 수거하는 방법으로 각각의 방법을 독립적으로 생각하여 풀었을 때

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

        for (int i = n - 1; i >= 0; i--) {
            if (deliveries[i] > 0 || pickups[i] > 0) 
            {
                totalDistance += (i + 1) * 2;
                int availableCapacity = cap;

                for (int j = i; j >= 0 && availableCapacity > 0; j--) {
                    if (deliveries[j] > 0) {
                        int deliverHandled = Math.Min(deliveries[j], availableCapacity);
                        deliveries[j] -= deliverHandled;
                        availableCapacity -= deliverHandled;
                    }
                }

                availableCapacity = cap;
                
                for (int j = i; j >= 0 && availableCapacity > 0; j--) {
                    if (pickups[j] > 0) {
                        int pickupHandled = Math.Min(pickups[j], availableCapacity);
                        pickups[j] -= pickupHandled;
                        availableCapacity -= pickupHandled;
                    }
                }
            }
        }

        return totalDistance;
    }
}

 

문제점 

-  각 배달과 수거 작업을 반복적으로 처리하는 점에서 시간 초과가 발생 (알고리즘은 큰 입력에 대해 비효율적)

 

2. 비효율적인 코드를 수정  

- 배달과 수거를 따로 두지 않고 한번에 처리 

using System;

public class Solution {
      public long solution(int cap, int n, int[] deliveries, int[] pickups) 
      {
            long totalDistance = 0;
            int deliveryIndex = n - 1;
            int pickupIndex = n - 1;

            while (deliveryIndex >= 0 || pickupIndex >= 0) 
            {
                while (deliveryIndex >= 0 && deliveries[deliveryIndex] == 0) 
                {
                    deliveryIndex--;
                }

                while (pickupIndex >= 0 && pickups[pickupIndex] == 0) 
                {
                    pickupIndex--;
                }

                if (deliveryIndex >= 0 || pickupIndex >= 0) 
                {
                    totalDistance += (Math.Max(deliveryIndex, pickupIndex) + 1) * 2;

                     // 배달 처리
                    int availableCapacity = cap;
                    while (deliveryIndex >= 0 && availableCapacity > 0) 
                    {
                        if (deliveries[deliveryIndex] > 0) 
                        {
                            int deliverHandled = Math.Min(deliveries[deliveryIndex], availableCapacity);
                            deliveries[deliveryIndex] -= deliverHandled;
                            availableCapacity -= deliverHandled;
                        }
                        if (deliveries[deliveryIndex] == 0) 
                        {
                            deliveryIndex--;
                        }
                    }

                    // 수거 처리
                    availableCapacity = cap;
                    while (pickupIndex >= 0 && availableCapacity > 0) 
                    {
                        if (pickups[pickupIndex] > 0) 
                        {
                            int pickupHandled = Math.Min(pickups[pickupIndex], availableCapacity);
                            pickups[pickupIndex] -= pickupHandled;
                            availableCapacity -= pickupHandled;
                        }
                        if (pickups[pickupIndex] == 0) 
                        {
                            pickupIndex--;
                        }
                    }
                }
            }
        
        	return totalDistance;
		}
    }

 

 

3. 개선된 점 

- 배달과 수거 총 두 개의 내부 for문을 사용

=> 배달/수거의 작업이 필요한 지 확인 후 한번에 수행 

 

- 배달과 수거의 값 0 확인도 루프 내에서 불필요하게 수행

=> while로 변경하여 작업이 끝난 후 인덱스를 효율적으로 줄여 불필요한 탐색 제거

 (for문 보다는 while이 동적인 종료 조건을 처리하는 데 유용하다고 판단, 탐색 범위를 유연하게 조정도 가능한 장점이 있어 변경)

 

- 매번 현재 집에서 배달/수거 작업이 필요하면 왕복 거리 계산

=>  Math.Max()를 통해 배달/수거 중 가장 먼 집을 기준 잡아 한번에 왕복 거리를 계산

 

- O(n^2)의 중복 탐색 발생 (모든 경우를 탐색하기 때문에 불필요한 방법)

=> O(n) 복잡도를 사용하여 한 번의 탐색으로 각 집의 작업을 처리