leetcode - Two City Scheduling

 

List<List<int>를 인자로 받습니다.

인자는 각 사람이 A 도시로 가는데 드는 비용, B 도시로 가는데 드는 비용을 의미합니다.

 

예제를 설명드리면 첫번째 사람이 A로 가는데 드는 비용은 10, B로 가는데 드는 비용은 20입니다.

 

각 사람은 짝수로 들어오고, A도시와 B도시에 동일하게 사람을 가도록 해야합니다.

이 조건에서 가장 적은 돈으로 보내도록 구하는것이 문제입니다.

 

사람마다 모두 A, B로 가는 금액은 다를것이고, 금액의 차가 큰것부터 보내면 최소금액으로 모두 각 도시로 보낼 수 있을겁니다.

그렇기 때문에, 저의 경우는 아래와 같이 풀었습니다.

 

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        res = 0
        a_count = b_count = int(len(costs) / 2)
        for cost in costs:
            cost.append(abs(cost[0] - cost[1]))
        sorted_costs = sorted(costs, key=lambda x:x[2], reverse=True)

        for cost in sorted_costs:
            if a_count == 0:
                res += cost[1]
                continue
            if b_count == 0:
                res += cost[0]
                continue
            if cost[0] < cost[1]:
                a_count -= 1
                res += cost[0]
            else:
                b_count -= 1
                res += cost[1]
        return res

 

• 각 사람의 A, B의 cost의 차를 구해 append 시킨다.
• 차가 큰순으로 정렬시킨다.
• 정렬된 사람들을 iterate 돌며 적은 비용을 선택한다.
  
  • 단, A,B에 모두 동일한 사람수를 보내야 하기 때문에 count를 세어 A에 절반을 보냈다면 어쩔수 없이 B를 선택하도록 한다. (반대의 경우도 마찬가지)

 

감사합니다.