Leetcode) 857. Minimum Cost to Hire K Workers

857. Minimum Cost to Hire K Workers

import heapq

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        N = len(quality)
        sortedQuality = [[wage[idx] / quality[idx] , quality[idx]] for idx in range(N)]
        sortedQuality.sort(key=lambda x : (x[0], x[1]))
        h = []
        
        answer = float('inf')
        max_q = float('inf')
        acc_q = 0
        for wagePerQuality, q in sortedQuality:
            max_q = -h[0] if len(h) > 0 else float('inf')
            if len(h) < k or max_q > q:
                acc_q += q
                heapq.heappush(h, -q)
                if len(h) > k:
                    acc_q += heapq.heappop(h)
            if len(h) == k:
                answer = min(answer, acc_q * wagePerQuality)
        
        return answer

풀이

1. 일단 문제 해석을 하자면 어떤 idx를 기준으로 그 k개의 worker그룹을 만드는데 그룹에 속할 수 있는 기준은 어떤 idx를 기준으로 어떤 조건을 만족해야 한다.

   • 조건은 인덱스가 idx가 아닌 인덱스 j가 wage[idx] / quality[idx] * quality[j] / wage[j] >= 1일때 이다.

   • 그러면 wage[idx]/ quality[idx]으로 배열을 만들고 오름차순으로 정렬하면 i < j인 모든 인덱스 i, j에 대해서 wage[j] / quality[j] * quality[i] / wage[i] >= 1 이 된다.

     그 이유는 wage[j] / quality[j] * quality[j] / wage[j]는 당연히 1이다. 그런데 quality[i] / wage[i] >= quality[j] / wage[j]이기 때문이다.

2. 이제 포함되는 조건을 쉽게 만족 할 수 있게 배열을 만들었으니 순회 하면서 최소값만 저장하여 마지막에 리턴하면된다.

   • 최소힙인 h에는 -q를 작은 순대로 정렬한다.
   • 그리고 len(h)가 k일때 최소값을 가질 수도 있게 되기 때문에 체크해준다.
   • 그리고 h에 포함되는 q보다 작은 값이 등장하면 바로 최대값을 제거하고 작은 값을 넣어준다.
   • acc_q는 h에 포함된 q의 합으로 len(h)가 k일때 사용하기 위해 계속 해서 갱신해준다.
   • 결국 답이 되는 값은 기준이 되는 idx의 wagePerQuality * (k그룹의 quality의 합 => acc_q) 중에서 최소값 이다.
   • 그래서 기준이 되는 wagePerQuality는 최소로 만들 수 없기 때문에 acc_q가 최소가 되게 h힙을 잘 갱신하면 된다.