[Leetcode] Two City Scheduling

solution for Two City Scheduling

 

 

Problem)

 

 

Solution)

문제에서 각 cost간의 차이 값을 구했을 때, 차이 값이 작으면 A 도시로 차이값이 크면 B 도시로 가는 것이 비용상 더 효율적이다.

즉 문제에서 제공한 예제에 적용해서 4명의 각 비용의 차이 값을 계산하면 [-10, -170, 350, 10]이 되고 이를 오름차순으로 정렬하면 [-170, -10, 10, 350]이 된다. 여기서 우리는 정렬된 리스트를 기준으로 좌측에서 A로 우측에서 B로 한명씩 보내게되면 최소 비용으로 모든 사람들을 A, B 도시로 반반씩 보낼 수 있게 된다.

 

특별한 알고리즘에 대한 지식보다는 문제에 대한 이해와 해석 능력이 필요한 문제인 것 같다.

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        N = len(costs)
        diff = [c[0] - c[1] for c in costs]
        indices =  sorted(range(0,N), key=lambda k:diff[k])
        result = 0
        
        for i in range(int(N/2)):
            result += costs[indices[i]][0]
            result += costs[indices[N-i-1]][1]
        return result

 

좀 더 파이썬 다운 코드...

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key = lambda x: x[0]-x[1])
        return sum(i[0] for i in costs[:len(costs)//2]) + sum(j[1] for j in costs[len(costs)//2:])