[Kotlin] 프로그래머스 - 택배 배달과 수거하기

문제

링크

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ cap ≤ 50

1 ≤ n ≤ 100,000deliveries의 길이 = pickups의 길이 = n

• deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
• pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
• 0 ≤ deliveries의 원소 ≤ 50
• 0 ≤ pickups의 원소 ≤ 50

트럭의 초기 위치는 물류창고입니다.

입출력 예

입출력 예 #1

• 입력
• cap: 4
• n: 5
• deliveries: [1, 0, 3, 1, 2]
• pickups: [0, 3, 0, 4, 0]
• 출력: 16

입출력 예 #2

• 입력
• cap: 2
• n: 7
• deliveries: [1, 0, 2, 0, 1, 0, 2]
• pickups: [0, 2, 0, 1, 0, 2, 0]
• 출력: 30

풀이

배달 및 수거할 택배가 i번째 집에 있다면, 반드시 한 번은 i번까지 가야 한다.

• 물류창고에서 출발하여 i번째 집까지 왕복해야 한다.

만일 한 번에 처리할 수 없는 양이면 전부 처리할 때까지 왕복해야 한다.

• 최소 이동 거리를 구해야하므로 가장 멀리에 있는 집부터 방문한다.

물류창고에서 출발하여 다시 되돌아오는 동안 cap개 만큼 배달과 수거를 동시에 처리할 수 있다.

• 가장 멀리있는 집부터 역순으로 배달하면서 빈 공간에 수거 택배를 채운다.

코드

class Solution {
    fun solution(cap: Int, n: Int, deliveries: IntArray, pickups: IntArray): Long {
        var answer: Long = 0

        var delivery = 0 // 남은 택배 상자
        var pickup = 0 // 남은 수거 상자

        // 무조건 왕복해야하기 때문에 가장 멀리 있는 집부터 거꾸로 방문
        for (i in n - 1 downTo 0) {
            // 배달 및 수거를 처리해야 하는 양
            delivery += deliveries[i]
            pickup += pickups[i]
            // 배달 및 수거를 전부 처리할 때까지 왕복
            while (delivery > 0 || pickup > 0) {
                delivery -= cap
                pickup -= cap
                // i+1번째 집과 물류창고를 왕복
                answer += (i + 1) * 2
            }
        }

        return answer
    }
}

테스트 1 〉	통과 (0.12ms, 58.3MB)
테스트 2 〉	통과 (0.06ms, 62.3MB)
테스트 3 〉	통과 (0.04ms, 62.1MB)
테스트 4 〉	통과 (0.05ms, 60.9MB)
테스트 5 〉	통과 (0.04ms, 61.4MB)
테스트 6 〉	통과 (0.04ms, 60.6MB)
테스트 7 〉	통과 (0.12ms, 62.3MB)
테스트 8 〉	통과 (0.16ms, 61.8MB)
테스트 9 〉	통과 (0.37ms, 63.2MB)
테스트 10 〉	통과 (0.60ms, 63.8MB)
테스트 11 〉	통과 (0.22ms, 65MB)
테스트 12 〉	통과 (0.28ms, 63.1MB)
테스트 13 〉	통과 (0.21ms, 63.9MB)
테스트 14 〉	통과 (0.16ms, 65.1MB)
테스트 15 〉	통과 (2.83ms, 69.6MB)
테스트 16 〉	통과 (12.00ms, 69.6MB)
테스트 17 〉	통과 (4.62ms, 69.6MB)
테스트 18 〉	통과 (3.27ms, 68.3MB)
테스트 19 〉	통과 (3.58ms, 69.6MB)
테스트 20 〉	통과 (3.28ms, 69.5MB)