C++로 K명의 작업자를 고용할 때 드는 최소 비용 구하기

문제 설명

N명의 작업자가 있다고 가정해 보겠습니다. 각 작업자는 '품질(quality)'이라는 지표를 가지며, i번째 작업자는 품질 값 quality[i]와 최저 임금 기대치 wage[i]를 갖습니다. 우리는 K명의 작업자를 고용하여 하나의 급여 그룹을 구성하려고 하며, 이때 다음 두 가지 규칙을 반드시 지켜야 합니다.

급여 그룹에 속한 각 작업자는 그룹 내 다른 작업자들과 비교한 자신의 품질 비율에 비례하여 급여를 받아야 합니다.
급여 그룹의 모든 작업자는 자신이 기대하는 최저 임금 이상을 받아야 합니다.

즉, 위 조건을 모두 만족하면서 급여 그룹을 구성하는 데 필요한 최소 금액을 찾는 것이 목표입니다.

예를 들어 입력이 quality = [10, 22, 5], wage = [70, 52, 30], K = 2라면 출력은 105.000이 됩니다. 첫 번째 작업자에게 70을, 세 번째 작업자에게 35를 지급하면 조건을 충족하면서 비용을 최소화할 수 있기 때문입니다.

해결 접근 방법

이 문제는 그리디(Greedy) 알고리즘과 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '임금 대비 품질 비율(wage/quality)'이 낮은 작업자부터 순서대로 살펴보는 것입니다. 특정 작업자를 기준 비율로 삼으면, 앞서 살펴본 비율이 더 낮은 작업자들은 해당 비율로 지급해도 최저 임금 조건을 만족하게 됩니다. 여기에 최대 힙(max-heap)을 사용해 현재까지의 후보 중 품질이 가장 높은(비용 부담이 큰) 작업자를 제거하면, 총 품질 합을 최소로 유지할 수 있습니다.

구체적인 단계는 다음과 같습니다.

q(품질), w(임금), r(임금 대비 품질 비율)을 담는 Data 구조체를 정의합니다.
n := quality 배열의 크기로 설정합니다.
크기 n인 Data 배열 v를 생성합니다.
i := 0부터 i < n까지 반복하며 다음을 수행합니다.
- v[i].q := quality[i]
- v[i].w := wage[i]
- v[i].r := v[i].w / v[i].q
r 값을 기준으로 배열 v를 오름차순 정렬합니다.
temp := 0, sum := 0, ans := 무한대(inf)로 초기화합니다.
우선순위 큐 pq를 하나 선언합니다.
i := 0부터 i < n까지 반복하며 다음을 수행합니다.
- pq의 크기가 k와 같다면:
  - x := pq의 최상단(top) 요소
  - sum := sum - x
  - pq에서 해당 요소를 제거
- pq의 크기가 k - 1과 같다면:
  - ans := min((sum × v[i].r) + v[i].w, ans)
- sum := sum + v[i].q
- v[i].q를 pq에 삽입
ans를 반환합니다.

여기서 sum에는 현재 선택된 k-1명의 품질 합이 저장되고, 여기에 현재 작업자의 비율 r을 곱하면 그룹 전체 급여가 계산됩니다. 현재 작업자 본인의 임금 v[i].w를 더하는 이유는, 본인의 비율이 그룹 내 최고이므로 최소한 자신의 최저 임금은 받아야 하기 때문입니다.

더 나은 이해를 위해 다음 구현 예시를 살펴보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct Data {
    double q, w, r;
};
class Solution {
    public:
    static bool cmp(Data a, Data b) { return a.r < b.r; }
    double mincostToHireWorkers(vector<int> &quality, vector<int>
    &wage, int k) {
        int n = quality.size();
        vector<Data> v(n);
        for (int i = 0; i < n; i++) {
            v[i].q = quality[i];
            v[i].w = wage[i];
            v[i].r = v[i].w / v[i].q;
        }
        sort(v.begin(), v.end(), cmp);
        double temp = 0;
        double sum = 0;
        double ans = INT_MAX;
        priority_queue<int> pq;
        for (int i = 0; i < n; i++) {
            if (pq.size() == k) {
                double x = pq.top();
                sum -= x;
                pq.pop();
            }
            if (pq.size() == k - 1) {
                ans = min((sum * v[i].r) + v[i].w, ans);
            }
            sum += v[i].q;
            pq.push(v[i].q);
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {10,22,5}, v1 = {70,52,30};
    cout << (ob.mincostToHireWorkers(v, v1, 2));
}

입력

{10,22,5}
{70,52,30}
2

출력

복잡도 분석

작업자 배열을 정렬하는 데 O(N log N)의 시간이 걸리고, 이후 각 작업자마다 우선순위 큐 연산이 O(log K)씩 발생하므로 전체 시간 복잡도는 O(N log N)입니다. 공간 복잡도는 Data 배열과 우선순위 큐를 위해 O(N)입니다.