[LeetCode] Two City Scheduling

https://leetcode.com/problems/two-city-scheduling/

Two City Scheduling - LeetCode

쉬운줄 알았는데 은근히 까다로운 문제다. 처음에는 DP인가? 했다가

완전탐색인가? 했는데 최대 연산이 200! / 100! * 100! 인걸 보고 아닌 것을 깨닫고 그리디로 풀어봤다.

 

일단 최소한의 비용이 드는 승객들을 더하고 균형을 맞출 때에는 A와 B의 차이가 적은 순서대로 더해줘서 맞추면 됨.

 

내 풀이

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        dataA = []
        dataB = []
        result = 0
        for cost in costs:
            if cost[0] < cost[1]:
                result += cost[0]
                dataA.append(cost[1]-cost[0])
            else:
                result += cost[1]
                dataB.append(cost[0]-cost[1])
        if len(dataA) != len(dataB):
            diff = len(dataA) - len(costs)//2 if len(dataA) > len(dataB) else len(dataB) - len(costs)//2
            result = result + sum(sorted(dataA)[:diff]) if len(dataA) > len(dataB) else result + sum(sorted(dataB)[:diff])
        return result

 

class Solution(object):
    def twoCitySchedCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        a = sorted(costs, key=lambda x: x[0]-x[1])
        cost = 0
        for i in range(len(a)//2):
        	cost += a[i][0] + a[-i-1][1]
        return cost