【프로그래머스】 택배 배달과 수거하기 (Kotlin)

문제

프로그래머스

 

풀이

트럭이 출발할 때마다 가장 먼 집부터 최대 적재량만큼 배달 및 수거해야 최소 이동 거리로 배달 및 수거를 마칠 수 있다.

 

배달 및 수거 큐 구성하기

deliveries와 pickups를 각각 거꾸로 순회하며 큐에 각 집을 방문해야 하는 횟수만큼 추가한다.

이 로직은 두 번 실행해야 하므로 IntArray가 파라미터인 로컬 함수로 작성한다.

val array: IntArray = /* deliveries 또는 pickups */

// 방문해야 하는 가장 먼 집을 담은 큐
val queue = LinkedList<Int>()

// 현재 트럭에 싣고 있는 상자 수
// 0이면 현재 집이 처음 방문한 집이라는 의미고,
// 그렇지 아니면 더 먼 집을 먼저 방문하고 여유가 있어 방문했다는 의미다.
var currentLoad = 0

// array를 거꾸로 순회한다.
for (i in n - 1 downTo 0) {

    // 배달 또는 수거할 상자가 없으면 건너뛴다.
    if (array[i] != 0) {
    
        // 배달 또는 수거해야 하는 총 상자 수
        val totalLoad = currentLoad + array[i]
        
        // 현재 집에 방문해야 하는 횟수
        val visits = (totalLoad / cap)
        
            // cap개씩 배달 또는 수거하고 상자가 남으면 한 번 더 방문해야 한다. 
            .plus(if (totalLoad % cap == 0) 0 else 1)
            
            // 다른 집을 먼저 방문했다면 방문 횟수를 줄인다.
            .minus(if (currentLoad == 0) 0 else 1)
            
        // cap개씩 배달 또는 수거하고 남은 상자만큼 싣게 된다.
        currentLoad = totalLoad % cap
        
        // 방문해야 하는 횟수만큼 큐에 추가한다.
        repeat(visits) { queue.add(i + 1) }
    }
}

 

총 이동 거리 계산하기

두 큐에서 각각 pop한 값을 비교하여 이동 거리 합계를 증가시킨다.

// 총 이동 거리
var answer = 0L

// 두 큐가 모두 비게 될 때까지 반복한다.
while (deliveryQueue.isNotEmpty() || pickupQueue.isNotEmpty()) {

    // 각 큐에서 pop한 값을 비교한다.
    // 한 쪽이 먼저 비게 되는 경우를 고려하여 poll()과 엘비스 연산자를 사용한다.
    // (poll()은 큐가 비어 있으면 null을 리턴)
    // 둘 중 큰 쪽이 배달 및 수거할 때 방문해야 하는 가장 먼 집(가장 큰 이동 거리)을 나타낸다.
    // 왕복 거리이므로 이에 2를 곱한 값만큼 총 이동 거리를 증가시킨다.
    answer += max(deliveryQueue.poll() ?: 0, pickupQueue.poll() ?: 0) * 2
}

 

코드

내 풀이

GitHub - blacksg/ProblemSolving

import java.util.LinkedList
import kotlin.math.max

class Solution {
    fun solution(cap: Int, n: Int, deliveries: IntArray, pickups: IntArray): Long {
        fun populateQueue(array: IntArray): LinkedList<Int> {
            val queue = LinkedList<Int>()
            var currentLoad = 0
            for (i in n - 1 downTo 0) {
                if (array[i] != 0) {
                    val totalLoad = currentLoad + array[i]
                    val visits = (totalLoad / cap)
                        .plus(if (totalLoad % cap == 0) 0 else 1)
                        .minus(if (currentLoad == 0) 0 else 1)
                    currentLoad = totalLoad % cap
                    repeat(visits) { queue.add(i + 1) }
                }
            }
            return queue
        }
        
        var answer = 0L
        val deliveryQueue = populateQueue(deliveries)
        val pickupQueue = populateQueue(pickups)
        while (deliveryQueue.isNotEmpty() || pickupQueue.isNotEmpty()) {
            answer += max(deliveryQueue.poll() ?: 0, pickupQueue.poll() ?: 0) * 2
        }
        return answer
    }
}

 

다른 풀이

다른 분의 풀이(C++)에서 변수 이름을 변경한 것이다.

다른 자료구조를 사용하지 않고 간결하며 훨씬 빠른 코드다.

GitHub - blacksg/ProblemSolving

class Solution {
    fun solution(cap: Int, n: Int, deliveries: IntArray, pickups: IntArray): Long {
        var answer = 0L
        var deliverySpace = 0
        var pickupSpace = 0
        for (i in n - 1 downTo 0) {
            if (deliveries[i] != 0 || pickups[i] != 0) {
                var visits = 0
                while (deliverySpace < deliveries[i] || pickupSpace < pickups[i]) {
                    visits++
                    deliverySpace += cap
                    pickupSpace += cap
                }
                deliverySpace -= deliveries[i]
                pickupSpace -= pickups[i]
                answer += (i + 1) * visits * 2
            }
        }
        return answer
    }
}