[C#] 택배 배달과 수거하기

소슬잎·2023년 11월 4일

눈물나는 코테 연습

프로그래머스 문제

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

풀이 후기

0. 잡담

이 문제 전에 원래 풀고 있던게 있었는데,

궁금해서 레벨을 보니까 4레벨짜리... 고민만 하다가 허탕쳤다.

1. 분석

맨 처음 글을 읽고 생각난 건 뒤에서부터 훑어야 편하겠다는 느낌. 먼 거리 (배열 뒤)에 있을수록 최대한 많이 일하고 오자. 즉, 뒤에서부터 최대 개수의 일을 하고 복귀하면 풀어지는 문제 아닐까?

using System;

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

		// 테스트 케이스에 [0, 0, 0] [0, 0, 0] 같은 것도 있음
        while (deliveries[lastHouse] == 0 && pickups[lastHouse] == 0)
        {
            lastHouse--;
            if(lastHouse == -1){
                return 0;
            }
        }

        while (lastHouse >= 0)
        {
            var deli = cap;
            var pick = cap;
            var index = lastHouse;
            answer += (lastHouse + 1) * 2;

            while ((deli > 0 || pick > 0) && index >= 0)
            {
                if (deli > 0 && deliveries[index] > 0)
                {
                    var min = Math.Min(deli, deliveries[index]);
                    deli -= min;
                    deliveries[index] -= min;
                }

                if (pick > 0 && pickups[index] > 0)
                {
                    var min = Math.Min(pick, pickups[index]);
                    pick -= min;
                    pickups[index] -= min;
                }

                while (deliveries[index] == 0 && pickups[index] == 0 && index == lastHouse)
                {
                    lastHouse--;
                }

                index--;
            }
        }

        return answer;
    }
}

그니까 이런 느낌으로 마지막 집에서 일 다하고, 그다음 집에서 할 일 하고... 느낌으로 구현했더니,

코드가 대충 맞긴 했다. 사실 테케 15를 보면 알고리즘이 틀린 것 같긴 한데, 대충 구현 방식은 비슷했으니 사소한 문제라고 생각한다.

2. 공략 읽어오기

원래 안보고 하루 이틀 걸리더라고 더 생각해서 푸는 게 좋다고 생각했는데, 실전 코테는 시간이 있어서 그 정도로 열심히는 안 하기로 했다.

질문하기에 있는 글을 읽어온 결과 다음과 같은 규칙이 있는 것을 배웠다.

효율적인 방법을 찾을 필요가 없다.
가장 효율적인 방법은 이 집에 놔두고, 이 집에 가져오고... 이런 방법을 굳이 안 찾아봐도 cap만큼 택배를 내리고 cap만큼 상자를 싣는 것. 테스트 케이스에서는 3개만 가져오는 것도 방법이지만 그냥 택배 5개 들고 나가는 것과 다름이 없다. 갈 때만 택배를 내릴 수 있다, 같은 제약도 없고 결과적으로 거리만 측정하기 때문이다.
마지막부터 지우는 게 효율적이다.
당연히 가장 먼 곳을 가장 적게 가는 게 정답.

마지막 지점을 지우려면 무조건 [deli or pick 중 큰 값 / cap]만큼 가긴 해야 한다.
마지막 집에 1개 택배, 100개 상자, 한번에 3개씩 옮긴다고 하면 그 집에 택배가 있든 없든 최소 34번은 마지막 집에 가야 한다. 남는 택배는 겸사겸사 딴 집에 배송시켜도 되고, 단순히 거리만 계산하기에 그냥 길 가다가 버린 걸로 판정해도 된다. 추가로 실행 시간을 크게 줄일 수도 있다.

0 ≤ deliveries의 원소 ≤ 50, 0 ≤ pickups의 원소 ≤ 50
위에 있는 주석처럼, 할 게 없는 테스트 케이스도 존재한다. 그런 거 생각 못하고 마지막 집은 무조건 방문한다는 가정하게 코드를 짰더니 좀 어지러웠다.

3. 실행 결과

해당 규칙에 맞게 다시 짜봤더니 다행이 통과했다. 4레벨 문제 풀다가 포기하고, 이것도 포기하면 엄청 허무할것 같았는데, 이정도면 괜찮은 듯.

4. 코드

using System;

public class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int lastHouse = n - 1;
        var leftDeli = 0;
        var leftPick = 0;

        while (lastHouse >= 0)
        {
            // 현재 집 배달에 필요한 수량은, 전에 배달하고 남은 수량 만큼을 빼야한다.
            var deli = Math.Max(0, deliveries[lastHouse] - leftDeli);
            var pick = Math.Max(0, pickups[lastHouse] - leftPick);
            leftDeli = Math.Max(0, leftDeli - deliveries[lastHouse]);
            leftPick = Math.Max(0, leftPick - pickups[lastHouse]);

            // 현재 집 배달은 둘 중 큰 값만큼 와야한다.
            var maxValue = Math.Max(deli, pick);

            // 가장 큰게 0이라면 올 필요없는 집임.
            if (maxValue == 0)
            {
                lastHouse--;
                continue;;
            }
            
            // 총 몇 번의 왕복이 필요한지 계산한다.
            var minLoop = maxValue / cap;
            if (maxValue % cap != 0)
            {
                minLoop++;
            }

            // 왕복 과정에서 몇개의 여유 자원이 남는지 계산한다.
            leftDeli += minLoop * cap - deli;
            leftPick += minLoop * cap - pick;
            
            // 왕복 시간을 계산.
            answer += (lastHouse + 1) * minLoop * 2;
            lastHouse--;
        }
        
        return answer;
    }
}