[leetcode] Two City Scheduling

문제

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

Two City Scheduling - LeetCode

내 풀이

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        
        answer = 0
        costs = sorted(costs, key = lambda x : -abs(x[0] - x[1]))
        n = len(costs) // 2
        cost_count = [n, n] # a,b
        for cost in costs:
            # a만 남음
            if cost_count[1] == 0:
                answer += cost[0]
            # b만 남음
            elif cost_count[0] == 0:
                answer += cost[1]
            # a > b
            elif cost[0] > cost[1]:
                answer += cost[1]
                cost_count[1] -= 1
            # a < b
            elif cost[0] < cost[1]:
                answer += cost[0]
                cost_count[0] -= 1
            # a = b
            else:
                answer+= cost[0]
                
        return answer

알게 된 것

힌트를 보고나서야 이해한 문제이다. 처음에는 DFS로 해버렸지만 당연히 TLE가 발생했다.

cost.length 가 100 이니까 최대 경우에 2^100 의  시간이 걸린다.

 

결론은 Greedy 하게 풀어야하는 문제였다.

핵심 개념은 "a_cost, b_cost 의 차이의 내림차순으로 정렬" 해야 한다는 것이다.

가장 큰 차이로부터 작은 값을 선택해나가다보면 어떤 상황에도 미니멀한 합을 구할 수 있게 된다.

앞으로도 배열을 순회하며 미래 상황을 예측할 수 없는 상황에서 현재 상황의 최적의 값을 찾아야하는 상황이라면 그리디를 고민해보자

 

피드백

A_cost == B_cost 일 때의 케이스를 고려했어야 했다.

역시 특정 케이스를 잘 테스트해놔야 겠다.

 

 

예시) [[10,10],[30,30],[40,40],[20,20]]