857. Minimum Cost to Hire K Workers

문제링크

설명

arr[i] 는 각각 i번째 노동자의 품질,월급을 나타내는 quality, wage 배열이 주어진다
가장 최소한의 비용으로 k 명을 고용할때 드는 비용을 구하여라

조건

• i번째 노동자를 고용하려면, 최소 wage[i] 보다 돈을 많이줘야됨
• 각 작업자의 월급은, quality에 정비례해야 함
• quality가 얼마던 간에 최소한의 비용이면 상관없음ㅋㅋ

---

💡풀이

가장 중요한건, 기준으로 삼을 작업자를 정하는 것이다

• 가장 효율적인 노예 작업자를 순서로 정렬한다 (돈을 적게 받고, 능률은 뛰어난 $\frac{quality}{weight}$)

  i번 노예는, 무조건 i+1번 노예가 받는 돈을 기준으로 했을때 만족하게 된다

• 효율적인 순서대로 k명을 뽑는다.

  이러면, 우리는 가장 효율적인 k을 고르게 된다

  사실, 효율은 정답과는 아무 상관이 없다.
  노예1이 노예2에 비해 아무리 효율이 좋아도, 노예2가 퀄리티가 낮아 돈을 덜 받으면 노예 2를 써야 한다

• 점점 비효율적인 얘들을 차례로 탐색하며, 최소값을 구한다

  사실, 효율적인 놈들 대신 비효율적인 애들을 쓸 경우는 퀄리티가 너무 높아서, 효율이 좋은데도 돈을 많이 받는 경우 이다

  따라서, 현재 뽑은 사람들 중 퀄리티가 제일 높은놈을 제외하고, i번째 비효율적인 놈 에 맞춰서 계산을 할 때, 총 월급이 더 적게 드는지를 계산하여 업데이트하면 된다.

---

전체코드

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:

        worker_len = len(quality)
        
        efficent_arr = sorted(
            [ (wage[i]/quality[i], quality[i]) for i in range(worker_len) ]
        )

        max_heap , all_quality =[],0

        for i in range(k): #(k개를 만족하는)가장 효율적 경우부터 
            all_quality += efficent_arr[i][1]
            heapq.heappush(    max_heap, - efficent_arr[i][1]            )

        answer = efficent_arr[i][0] * all_quality # 가장 효율적인 팀은 구성했을때의 총 금액
 

        # 비 효율적이여도, quality가 낮으면, 필요한 돈은 오히려 적을 수 있음
        for i in range(k, worker_len):
            
            ith_worker_efficent, ith_worker_quality = efficent_arr[i][0], efficent_arr[i][1]
            
            # 가장 높은 quality를  대채한 후, [i]번째 효율적인 놈을 기준으로 계산하여 정답 업데이트
            most_quality = -heapq.heappop(max_heap)
            all_quality -= most_quality
            all_quality += ith_worker_quality
            
            heapq.heappush(max_heap,-ith_worker_quality)

            answer = min(answer, ith_worker_efficent*all_quality)

        return answer