문제 링크

카카오 코딩테스트: 택배 배달과 수거하기

문제 분석

멀리 있는 집을 먼저 방문하는 것이 이득이기 때문에, 이 문제는 딱 봐도 “그리디다!”를 떠올렸다. 그러나, 스택을 쓰는 것까지는 도달하지 못했다.

  1. 배달 및 수거할 택배 상자가 남은 가장 먼 집부터 택배를 배달 및 수거합니다.

  2. 트럭이 물류창고에서 출발해 가장 먼 집으로 이동할 때는 배달만 하고, 다시 물류창고로 돌아올 때는 수거만 합니다.

  3. 트럭이 물류창고에서 출발할 때 항상 택배를 최대 개수만큼 배달하고, 물류창고로 돌아갈 때 최대 개수만큼 수거합니다.

  4. 집 번호와 해당 집에 배달할 택배 개수를 집 번호가 작은 순서대로 배달 스택에 담습니다.

  5. 집 번호와 해당 집에 수거할 빈 택배 개수를 집 번호가 작은 순서대로 스택에 담습니다.

  6. 배달 스택에서 가장 위에 위치한 원소의 집 번호와 수거 스택에서 가장 위에 위치한 원소의 집 번호를 비교해 큰 값의 두 배만큼 answer에 더합니다. 이 때 두 배를 더하는 이유는 트럭이 물류창고부터 가장 먼 집까지 왕복하기 때문입니다.

  7. 이번에 배달 가능한 개수가 0이 되거나 배달 스택이 빌 때까지 배달 스택에서 남은 배달을 처리합니다.

  8. 이번에 수거 가능한 개수가 0이 되거나 수거 스택이 빌 때까지 수거 스택에서 남은 수거를 처리합니다.

  9. 배달 스택과 수거 스택이 모두 빌 때까지 3, 4, 5 과정을 반복합니다.

이 때, cap 보다 스택 top의 개수가 더 크다면, 해당 집은 아직 배달/수거가 안끝났다는 걸 주의해야함.

각 집에서 배달 및 수거할 택배 상자의 최대 개수와, 트럭에 실을 수 있는 택배 상자의 최대 개수 cap는 모두 50 이하. 이를 상수 취급하면, 이 알고리즘의 시간 복잡도는 O(n)이다. (n = 배달 및 수거할 집의 개수)

내 코드

import Foundation

struct House {
    let number: Int
    var quantity: Int
}

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    var answer: Int64 = 0
    var stk1: [House] = []   // 배달
    var stk2: [House] = []    // 수거
    
    // 집번호 작은 것부터 (집번호 멀리 있는 것이 스택의 위에 가도록)
    for (i, d) in deliveries.enumerated() where d > 0 {
        stk1.append(House(number: i + 1, quantity: d))
    }
    for (i, p) in pickups.enumerated() where p > 0 {
        stk2.append(House(number: i + 1, quantity: p))
    }
    
    while !stk1.isEmpty || !stk2.isEmpty {
        
        answer += Int64(max(stk1.last?.number ?? 0, stk2.last?.number ?? 0) * 2)
        
        var c = cap
        while(c > 0 && !stk1.isEmpty) {
            let idx = stk1.count - 1
            if stk1[idx].quantity > c {
                stk1[idx].quantity -= c
                c = 0
            } else {
                c -= stk1[idx].quantity
                stk1.removeLast()
            }
        }
        
        c = cap
        while(c > 0 && !stk2.isEmpty) {
            let idx = stk2.count - 1
            if stk2[idx].quantity > c {
                stk2[idx].quantity -= c
                c = 0
            } else {
                c -= stk2[idx].quantity
                stk2.removeLast()
            }
        }
    }
    return answer
}

배운 점

그리디 알고리즘을 써야겠다는 아이디어에서 나아가, 스택 자료구조를 사용하면 멀리있는 집부터 가까운집까지 차례대로 처리 가능하다는 것.

매 라운드마다 answer에 더해지는 값은 왕복이므로 멀리있는 수거 집과 택배 집 중 큰 값에 *2 를 해야 한다는 것.

리팩토링 코드

정리