[Algorithm/Swift] 프로그래머스(Lv.2) - 택배 배달과 수거하기

안녕하세요 제인입니다 :)

요즘 PS를 연습하며 아이디어를 코드로 구현하는 능력이 부족하다는 것을 깨닫고 있는데요,,,

차근차근 기록도 해가며 실력을 높여가야겠습니다..!!

Greedy 유형인 2023 KAKAO BLIND RECRUITMENT - 택배 배달과 수거하기 문제 풀이를 정리해보겠습니다😊

문제 링크

프로그래머스

문제 풀이

처음 접근

일단 문제를 읽고 그리디로 풀어야겠다는 아이디어는 떠올랐는데, 스택 자료구조를 이용해야겠다는 생각은 하지 못해 방문 처리 및 조건을 판단해주기가 까다롭다고 느꼈습니다🥲 (택배 수거 시 배열의 요소를 0으로 바꿔주고 또 다시 방문해야 할 집을 확인하는 식으로 풀었거든여..)

그리디 + 스택을 활용한 풀이

최종적으로 구해야 하는 값은 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리이기 때문에 그리디 전략으로 매 순간 최소 이동 거리를 구해 최종적인 값까지 구하면 됩니다.

 

이 때, 문제에서 제시된 조건을 확인해보면 한 사이클을 왕복 한 번으로 잡아야 한다는 것을 파악할 수 있습니다. (창고에서 출발해 돌아와야하기 때문) 

한 사이클 동안 최대로 배달, 최대로 수거(cap 만큼)를 하면 한 사이클의 최소 이동거리를 구할 수 있고, 사이클 반복 횟수를 최대로 줄이는 방식으로 최종적인 값을 구할 수 있습니다.

 

정리해보자면, 다음과 같이 트럭을 움직이면 됩니다.

1. 배달 및 수거할 택배 상자가 남은 가장 먼 집부터 택배를 배달 및 수거합니다.
2. 트럭이 물류창고에서 출발해 가장 먼 집으로 이동할 때는 배달만 하고, 다시 물류창고로 돌아올 때는 수거만 합니다.
3. 트럭이 물류창고에서 출발할 때 항상 택배를 최대 개수(cap)만큼 배달하고, 물류창고로 돌아갈 때 최대 개수(cap)만큼 수거합니다.

 

항상 창고에서 가장 먼 집부터 배달하고, 수거하기 때문에 스택 자료구조를 이용해서 완료된 집은 pop하는 방삭으로 배달 or 수거 완료 여부를 쉽게 파악할 수 있습니다. (배달 스택, 수거 스택 하나씩 총 두 개의 스택 이용)

 

이러한 아이디어를 코드로 구현하면 다음과 같습니다.

Swift 풀이 코드

import Foundation

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    var deliveries = deliveries
    var pickups = pickups
    var result = 0
    
    while !deliveries.isEmpty || !pickups.isEmpty {
        deliveries.trimZeroSuffix()
        pickups.trimZeroSuffix()
        
        result += max(deliveries.count, pickups.count) * 2 // 이동거리는 항상 가장 먼거리의 2배
        var load = cap // 트럭에 실린 상자
        while !deliveries.isEmpty {
            if deliveries.last! > load {
                deliveries[deliveries.count-1] -= load
                break
            } else {
                load -= deliveries[deliveries.count-1]
                deliveries.removeLast()
            }
        }
        
        load = cap // 수거할 수 있는 택배 개수 최대로 채워줌
        while !pickups.isEmpty {
            if pickups.last! > load {
                pickups[pickups.count-1] -= load
                break
            } else {
                load -= pickups[pickups.count-1]
                pickups.removeLast()
            }
        }
    }
    
    return Int64(result)
}

extension Array where Element == Int {
    mutating func trimZeroSuffix() {
        while self.last ?? -1 == 0 {
            let _ = self.removeLast()
        }
    }
}

 

---

[참고 자료]

2023 카카오 신입 공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

[프로그래머스]택배 배달과 수거하기(Swift)

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