[LeetCode] 857. Minimum Cost to Hire K Workers (Java)

✅ 문제

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

1. Every worker in the paid group must be paid at least their minimum wage expectation.
2. In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.

Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within $10^{-5}$ of the actual answer will be accepted.

n명의 노동자가 존재한다. 두 개의 정수 배열인 quality과 wage가 주어지는데, 여기서 quality[i]는 i번째 노동자의 품질이고 wage[i]는 i번째 노동자의 최저 임금 기대치이다.

정확히 k명의 근로자를 고용하여 유급 집단을 구성하고자 한다. k명의 근로자를 고용하기 위해서는 다음과 같은 규칙에 따라 급여를 지급해야 한다:

1. 임금을 받는 집단에 속한 모든 노동자는 최소한 최저임금 기대 이상의 임금을 받아야 한다.
2. 집단 내에서 각 노동자의 임금은 그들의 품질과 정비례해야 한다. 즉, 한 노동자의 품질이 집단 내 다른 노동자의 품질의 두 배라면, 그들은 다른 노동자의 두 배의 임금을 받아야 한다.

정수 k가 주어졌을 때 _위 조건을 만족하는 집단을 구성하는 데 필요한 최소 금액_을 반환한다. 실제 답변에서 $10^{-5}$ 이내의 답변은 수용하게 된다.

✅ 풀이

import java.util.*;

class Solution {
    public class Worker {
        Worker(int quality, double perCost) {
            this.quality = quality;
            this.perCost = perCost;
        }
        double quality, perCost;
    }

    private double minSum = Double.MAX_VALUE;

    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length; //노동자 수
        double minSum = Double.MAX_VALUE; //최소 금액

        Worker[] workers = new Worker[n]; //임금 기대치를 계산할 노동자 배열
        for(int i = 0; i < n; i++) {
            workers[i] = new Worker(quality[i], (double) wage[i] / quality[i]);
        }

        //품질에 따른 임금 기대 비율을 오름차순으로 정렬
        Arrays.sort(workers, Comparator.comparingDouble(o -> o.perCost));
        double qualitySum = 0; //품질 합계
        PriorityQueue<Double> pq = new PriorityQueue<>(Collections.reverseOrder()); //품질 내림차순 삽입
        for(int i = 0; i < n; i++) {
            pq.add(workers[i].quality); //i번째 노동자의 품질 삽입
            qualitySum += workers[i].quality; //더하기

            if(pq.size() == k) { //현재까지 Queue에 담긴 k명의 노동자 수
                minSum = Math.min(qualitySum * workers[i].perCost, minSum); //해당 기대비율에 속하는 k명의 최소임금자 계산
                qualitySum -= pq.poll(); //가장 높은 품질 (비싼 임금) 제외
            }
        }

        return minSum;
    }
}

🗄️ 노동자 배열의 정렬 방식

worker 배열은 품질에 따른 임금 기대 비율 기준으로 오름차순 정렬 되어있다.
그러므로 Queue에 i번째 노동자를 담았을 때,
이미 담긴 1 ~ (i - 1)번째의 노동자들은 i번째 노동자보다 임금 기대 비율이 낮다.

 

그 예시로 LeetCode 에 주어진 Test Case를 활용해보자면,

[10, 20, 5] //quality
[70, 50, 30] //wage
2 //k

1. 0번째 노동자의 품질은 10, 기대 임금은 70이다.
   그러므로 해당 노동자는 품질 1 당 7의 임금을 바라는 것이다.
2. 1번째 노동자의 품질은 20, 기대 임금은 50이다.
   해당 노동자는 품질 1 당 2.5의 임금을 바란다.
3. 마찬가지로 2 번째 노동자의 품질은 5, 기대 임금은 30이고
   해당 노동자는 품질 1 당 6의 임금을 바라는 것이다.

그렇다면 worker 배열은 1번째 노동자, 2번째 노동자, 0번째 노동자 순으로 정렬될 것이다.

🔀 Priority Queue 사용법

본격적으로 Priority Queue를 활용해 최소 비용을 구하는 방법을 알아보자.
위에서 설명하였듯이 이미 Queue에 있는 노동자들은 담을 노동자들보다 임금 기대 비율이 낮다.
이 말은 즉, 현재 담은 노동자의 기대 비율로 각 품질에 따른 월급을 계산하였을 때
다른 노동자의 기대 비율은 무조건 만족시킨다는 것이다.

 

임금 기대 비율 오름차순으로 Queue에 노동자의 품질을 삽입하고,
원하는 노동자의 수 k 명을 선택하였을 때
선택된 노동자 중 가장 높은 기대 비율을 가지고 있는 노동자(마지막 삽입 노동자) 기준으로
품질에 따른 임금 값을 계산하여 모두의 기대 임금을 충족시키는 금액을 도출한다.

(품질의 합) * (가장 높은 기대 비율)
⟹ qualitySum * workers[i].perCost

 

이 때 품질 내림차순의 Priority Queue를 사용하는 이유는
현재 기대 비율을 만족하는 모든 노동자가 있을 때
품질 당 계산 금액은 결국 동일하기 때문에 품질이 낮은 노동자를 선택함으로서 금액을 줄이는 것이다.

 

다시 한 번 LeetCode 에 주어진 Test Case를 활용해보았을 때,

[10, 20, 5] //quality
[70, 50, 30] //wage
2 //k

정렬된 노동자 [1, 2, 0]의 디버깅을 해보자면

1. 먼저 1번째 노동자의 품질이 pq에 삽입된다. pq의 크기는 현재 1( < k)이고, 가장 높은 품질 당 기대 비율은 가장 마지막으로 삽입된 1번째 노동자의 품질 당 비율인 2.5이다.
   ※ 이후 품질 당 기대 비율은 $2.5/1q$와 같은 형식으로 기입한다.
2. 이후 다음 순서인 2번째 노동자의 품질이 pq에 삽입된다. pq의 크기는 현재 2(= k)이므로 금액 도출이 가능하다. $6/1q$ 기준으로 지급 금액을 계산해보면
   $(20 * 6) + (5 * 6) = (20 + 5) * 6 = 150$
   150의 금액을 지불해야 pq에 삽입되어 있는 [1, 2] 노동자를 고용할 수 있다.
3. 현재 pq에 삽입되어있는 모든 노동자들은 이후 삽입될 노동자들의 품질 당 기대 비율에 따른 임금이 기대 임금을 무조건 넘는다. 그러므로 같은 품질 당 기대 비율로 계산한다면 품질이 떨어지는 노동자가 임금이 더욱 저렴할 것이다.
   때문에 품질이 20인 1번째 노동자가 품질이 5인 2번째 노동자보다 품질이 좋으므로 1번째 노동자를 더이상 계산하지 않는다. (pq.poll())
4. 마지막 순서인 0번째 노동자의 품질이 삽입되면 pq는 [2, 0] 노동자의 품질을 담고 있을 것이다. pq의 크기 2에서 1번째 노동자를 제외하고 0번째 노동자를 삽입했으므 pq의 크기는 여전히 2(= k)이다.
   마지막으로 삽입된 0번째 노동자의 기대 비율에 따라 $7/1q$ 기준으로 지금 금액을 계산하면
   $(5 * 7) + (10 * 7) = (5 + 10) * 7 = 105$
   105의 금액을 지불해야 [2, 0] 노동자를 고용할 수 있고, 이는 이전에 계산한 150보다 작은 수이므로 최소 금액은 105로 변경된다.

결론적으로 해당 TestCase의 정답은 105가 된다.
결국 품질 당 비율에 해당하는 모든 노동자들 중 가장 품질이 낮은 노동자 k명을 찾으면 되는 문제인 것이다.