C# 택배 배달과 수거하기 - 그리디 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/150369

 

 

나의 코드

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

    int deliverIndex = Array.FindLastIndex(deliveries, (f) => f != 0); // 가장 먼 집부터 배달가야 함.
    int pickupIndex = Array.FindLastIndex(pickups, (f) => f != 0); // 가장 먼 집부터 회수해야 함.

    while(deliverIndex >= 0 || pickupIndex >= 0)
    {
        // 가는 길 : 배달 해야하는 가장 먼 지점부터 채워나감
        int deliverDist = 0;
        if(deliverIndex >= 0)
        {
            while(deliverIndex >= 0 && deliveries[deliverIndex] == 0)
                --deliverIndex;

            deliverDist = deliverIndex + 1;
            int curBox = cap; // 현재 담은 용량. 최대치만큼 담음.

            while(curBox > 0 && deliverIndex >= 0)
            {
                if(deliveries[deliverIndex] == 0)
                {
                    --deliverIndex;
                    continue;
                }

                int landedBox = Math.Min(deliveries[deliverIndex], curBox);
                deliveries[deliverIndex] -= landedBox;
                curBox -= landedBox;
            }
        }

        // 오는 길 : 역시 가장 먼 지점부터 회수 함
        int pickupDist = 0;
        if(pickupIndex >= 0)
        {
            while(pickupIndex >= 0 && pickups[pickupIndex] == 0)
                --pickupIndex;

            pickupDist = pickupIndex + 1;
            int curEmptyBox = cap; // 최대치만큼 담을 수 있음.

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

                int landedBox = Math.Min(pickups[pickupIndex], curEmptyBox);
                pickups[pickupIndex] -= landedBox;
                curEmptyBox -= landedBox;
            }
        }

        answer += Math.Max(deliverDist, pickupDist); // 가는 거리
    }
    return answer * 2; // 왕복 거리
}

문제의 핵심. 

1. 배달을 가야하는 곳 중 가장 먼 곳 부터 수행하면 맨 끝점까지 가면서 모든 상자를 내리고, 돌아올 때는 수거하면서 돌아온다면 배달상자와 수거상자는 서로 영향을 받지않는다.

2. 배달해야 되는 곳보다 수거해야하는 곳이 더 멀 수도 있다. 이 경우 두 곳 중 더 먼 곳으로 갔다가 돌아오면 된다. (그리디)

3. 모든 배달/수거가 끝난 시점에서 돌아와야하므로. 배달은 언제나 왕복으로 수행된다.

 

 

다른사람 풀이

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

    for(int i = n - 1; i >= 0; --i)
    {
        if(deliveries[i] == 0 && pickups[i] == 0)
            continue;

        int repeat = 0;
        while(deliver < deliveries[i] || pick < pickups[i])
        {
            deliver += cap;
            pick += cap;
            ++repeat;
        }

        deliver -= deliveries[i];
        pick -= pickups[i];

        answer += ((long)(i + 1) * repeat);
    }

    return answer * 2; // 왕복 거리
}

1. 배달과 회수를 동시에 처리함.

2. 각 계산시 Math.Min 으로 처리하지 않고 쌩으로 cap을 더한 뒤, 그 값을 유지해서 다음 배달에 사용함.