[Algorithm] 택배 배달과 수거하기

[hwangJi-dev]

💬 문제

택배 배달과 수거하기

💬 Idea

아이디어: 가장 먼 곳으로부터 cap개를 포함할 수 있을만큼 택배를 갖고 출발하여 가장 먼 곳부터 택배를 배달하고, 오는 길에 택배를 수거할 수 있을만큼 최대로 수거하자.

• stack 2개를 사용한다 → 배달 스택 / 수거 스택
  • 가장 가까운 집의 배달, 수거 정보부터 스택에 저장해둔다.
• 배달 스택과 수거 스택의 가장 위 요소들의 인덱스 정보를 비교하여 가장 먼 거리까지 이동한다.
• 이후 배달 스택이 비어있지 않으면서 이번에 배달가능한 개수일때까지 배달 스택을 돌며 배달 가능한 집에 배달을 한다.
• 수거도 동일.
• 위 과정을 스택이 빌 때까지 반복한다.

💬 풀이

func solution(cap:Int, n:Int, deliveries:[Int], pickups:[Int]) -> Int64 {
    var deliverStack: [(Int, Int)] = []
    var pickupStack: [(Int, Int)] = []
    var distance = 0
    
    for i in 0..<n {
        if deliveries[i] != 0 {
            deliverStack.append((i, deliveries[i]))
        }
        
        if pickups[i] != 0 {
            pickupStack.append((i, pickups[i]))
        }
    }
    
    while !deliverStack.isEmpty || !pickupStack.isEmpty {
        let deliverLastIdx = deliverStack.last?.0 ?? 0
        let pickupLastIdx = pickupStack.last?.0 ?? 0
        
				// 거리 계산 (왕복)
        if deliverLastIdx > pickupLastIdx {
            distance += (deliverLastIdx + 1) * 2
        } else {
            distance += (pickupLastIdx + 1) * 2
        }
        
        var deliverBox = cap
        var pickupBox = cap
        
        while deliverBox > 0 && !deliverStack.isEmpty {
            if deliverBox - (deliverStack.last?.1 ?? 0) < 0 {
                deliverStack[deliverStack.count - 1].1 -= deliverBox
                break
            } else {
                deliverBox -= deliverStack.popLast()?.1 ?? 0
            }
        }
        
        while pickupBox > 0 && !pickupStack.isEmpty {
            if pickupBox - (pickupStack.last?.1 ?? 0) < 0 {
                pickupStack[pickupStack.count - 1].1 -= pickupBox
                break
            } else {
                pickupBox -= pickupStack.popLast()?.1 ?? 0
            }
        }
    }
    
    return Int64(distance)
}