택배 배달과 수거 - Kotlin

프로그래머스

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

 

배달 및 수거할 재활용 택배 상자 개수

배달 및 수거 과정

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

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

 

나의 풀이

  이 문제는 문제에 있는 예시대로 가장 멀리 있는 집부터 택배 상자를 배달, 수거해야 한다. 그래서 나는 stack을 Pair의 형태로 만들어 배달 정보와 수거 정보를 한번에 stack에 넣어주었다. 나는 마지막 집에서부터 최대 어디까지 배달, 수거를 할 수 있는지 계산하기 위해 stack에서 하나씩 poll을 하고 그 값들을 변수를 통해 더해주었다. 더해준 값이 만약 실을 수 있는 최대량을 넘었다면, 계산을 종료하고 마지막 값을 다시 stack의 추가해 주었다. 다만 만약 아직 실을 수 있는 양이 남아있다면 그 값을 빼고 stack에 추가해 주었다. 

import java.util.Stack

class Solution {
    fun solution(cap: Int, n: Int, deliveries: IntArray, pickups: IntArray): Long {
        var answer: Long = 0
        val stack = Stack<Pair<Int, Int>>()
        var check = true

        for (i in 0 until n) {
            // 배달을 할 택배와 수거할 빈 상자가 없는 경우에는 0을 리턴한다.
            if (deliveries[i] != 0) check = false
            if (pickups[i] != 0) check = false
            stack.push(deliveries[i] to pickups[i])
        }
        if (check) return 0

        // index는 어디서부터 택배를 배달하거나 수거해야 하는지를 알려준다.
        var index = n
        while (stack.isNotEmpty()) {
            var deliverCnt = 0
            var pickupCnt = 0
            var cnt = 0
            while (stack.isNotEmpty()) {
                val now = stack.pop()
                deliverCnt += now.first
                pickupCnt += now.second
                cnt++
                if (deliverCnt > cap || pickupCnt > cap) {
                    deliverCnt -= now.first
                    pickupCnt -= now.second
                    stack.push(now.first - (cap - deliverCnt) to now.second - (cap - pickupCnt))
                    cnt--
                    break
                }
            }
            answer += index * 2
            index -= cnt
        }
        return answer
    }
}

 

다른 사람의 풀이

 내가 푼 방식이랑 논리는 비슷하지만 너무 단순하게 문제를 해결한 풀이가 있어서 첨부한다.

class Solution {
    fun solution(cap: Int, n: Int, deliveries: IntArray, pickups: IntArray): Long {
        var answer: Long = 0
        var give = 0
        var get = 0
        for (i in n downTo 1) {
            val delivery = deliveries[i-1]
            val pickup = pickups[i-1]
            if (delivery != 0 || pickup != 0) {
                var cnt = 0
                while (delivery > give || pickup > get) {
                    ++cnt
                    give+=cap
                    get+=cap
                }
                give-=delivery
                get-=pickup
                answer+=(i*2*cnt)
            }
        }
        return answer
    }
}