1029. Two City Scheduling

출처: leetcode.com/problems/two-city-scheduling/

분류: Greedy, Easy

---

접근방식

각 cost에는 A와 B에 보낼 수 있는 비용이 들어있습니다.
2N개의 비용이 적힌 costs에서 각각 N개씩 공평하게 A와 B에 나눌 때 최소비용을 찾는 문제입니다.

costs가 [[10,20],[30,200],[400,50],[30,20]] 이렇게 주어져 있다면,
A에 2개 B에 2개를 [ 10, 30, 50, 20 ]로 뽑아줄 때 가장 최소비용이 됩니다.
하지만 무작정 둘 중 최소를 찾아서 분배한다고 해서 최소비용을 보장할 수가 없습니다.

costs 중에서 어떤 cost를 우선적으로 분배해줘야 할까요?  

바로 둘의 차이가 큰 cost를 먼저 분배해줘야 나중에 더 작은 비용을 분배할 수 없는 상황이 와도 손해를 최소화 할 수 있습니다.

 

해결방법

따라서 저는 |a-b| 으로 costs를 정렬해주는 방식으로 해결했습니다.
정렬한 후에는 a와 b의 개수가 다 찰 때까지 둘 중 더 최소 비용을 선택해줍니다.

func twoCitySchedCost(_ costs: [[Int]]) -> Int {

    let orderCosts = costs.sorted { (n1, n2) -> Bool in
        let absN1 = abs(n1[0] - n1[1])
        let absN2 = abs(n2[0] - n2[1])
        return absN1 > absN2
    }

    var aCount = 0
    var bCount = 0
    var totalCost = 0

    for cost in orderCosts {
        if (bCount < costs.count/2 && cost[1] <= cost[0]) || aCount >= costs.count/2 {
            totalCost += cost[1]
            bCount += 1
        } else {
            totalCost += cost[0]
            aCount += 1
        }
    }
    return totalCost
}

다른 분들의 풀이를 보니 우선 A나 B의 합에다가 
둘의 차이 오름차순으로 정렬해 절반만큼을 빼서 계산하는 방법도 있었습니다.

func twoCitySchedCost(_ costs: [[Int]]) -> Int {
    
    let costA = costs.map { $0[0] }
    var sumA = costA.reduce(0, +)
    
    let orderedDiff = costs.map { $0[1] - $0[0] }.sorted(by: <)
    for i in 0..<orderedDiff.count/2 {
        sumA += orderedDiff[i]
    }
    
    return sumA
}

 

두번째 방법이 보기엔 더 간단하지만, 첫번째 방법보다 시간이나 효율면에서 좋지는 못했습니다.

아마 한 종류로 뽑고 합하고, 차이를 구하느라 한번 더 돌고 정렬하고 다시 더해주는 과정이 더 들어가서 그런 것 같습니다.

 

배운점

그리디는.. 어렵다.. 알고리즘은 어렵다

잘하고싶다