Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 최대 이익 작업 배정 문제

문제 개요

각 작업에는 두 가지 정보가 주어집니다. difficulty[i]는 i번째 작업의 난이도를 나타내고, profit[i]는 해당 작업을 완료했을 때 얻는 수익을 나타냅니다. 또한 여러 명의 작업자가 있으며, worker[i]는 i번째 작업자의 능력을 의미합니다. 즉, 이 작업자는 난이도가 worker[i] 이하인 작업만 수행할 수 있습니다.

여기서 중요한 조건은 다음과 같습니다.

  • 각 작업자는 최대 한 개의 작업만 맡을 수 있습니다.
  • 하지만 하나의 작업은 여러 작업자가 중복해서 수행할 수 있습니다.

목표는 작업자들에게 작업을 적절히 배정하여 얻을 수 있는 최대 총 수익을 구하는 것입니다.

예시

입력이 다음과 같다고 가정해 보겠습니다.

difficulty = [2,4,6,8,10]
profit = [10,20,30,40,50]
worker = [4,5,6,7]

이 경우 출력은 100입니다. 작업자들에게 난이도 [4, 4, 6, 6]에 해당하는 작업을 배정하면 수익 [20, 20, 30, 30]을 얻게 되고, 이를 모두 더한 값이 100이기 때문입니다.

해결 전략

이 문제는 정렬과 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. 작업자 배열을 오름차순으로 정렬합니다.
  2. (난이도, 수익) 쌍으로 이루어진 작업 목록을 만든 뒤 난이도 기준으로 정렬합니다.
  3. 능력이 낮은 작업자부터 순서대로 처리하면서, 해당 작업자가 수행할 수 있는 작업 중 가장 높은 수익(maxVal)을 추적합니다.
  4. 작업자마다 현재까지의 maxVal을 더해 답을 누적합니다.

작업자를 능력순으로 정렬했기 때문에, 앞선 작업자가 수행 가능한 작업은 뒤의 작업자도 반드시 수행할 수 있습니다. 따라서 maxVal을 매번 초기화하지 않고 계속 유지하며 업데이트만 하면 됩니다.

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

  • ans := 0으로 초기화하고, n := profit 배열의 크기로 설정
  • worker 배열 정렬
  • (난이도, 수익) 쌍을 저장할 리스트 v 생성
  • i를 0부터 n-1까지 반복하며 (difficulty[i], profit[i])를 v에 삽입
  • v를 정렬
  • maxVal := 0, m := worker 배열의 크기, j := 0으로 초기화
  • i를 0부터 m-1까지 반복:
    • j < n이고 v[j].first <= worker[i]인 동안:
      • maxVal := max(maxVal, v[j].second)
      • j를 1 증가
    • ans := ans + maxVal
  • ans 반환

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int ans = 0;
        sort(worker.begin(), worker.end());
        vector<pair<int, int>> v;
        int n = profit.size(); // 작업의 개수
        for(int i = 0; i < n; i++){
            v.push_back({difficulty[i], profit[i]});
        }
        sort(v.begin(), v.end());
        int maxVal = 0;
        int m = worker.size(); // 작업자의 수
        int j = 0;
        for(int i = 0; i < m; i++){
            while(j < n && v[j].first <= worker[i]){
                maxVal = max(maxVal, v[j].second);
                j++;
            }
            ans += maxVal;
        }
        return ans;
    }
};
int main() {
    Solution ob1;
    vector<int> difficulty{2,4,6,8,10};
    vector<int> profit{10,20,30,40,50};
    vector<int> worker{4,5,6,7};
    cout << ob1.maxProfitAssignment(difficulty, profit, worker) << endl;
    return 0;
}

실행 결과

입력

[2,4,6,8,10]
[10,20,30,40,50]
[4,5,6,7]

출력

100

복잡도 분석

시간 복잡도는 작업 목록 정렬에 O(n log n), 작업자 정렬에 O(m log m)이 소요되고, 이후 투 포인터 방식의 순회에 O(n + m)이 걸리므로 전체적으로 O(n log n + m log m)입니다. 공간 복잡도는 작업 쌍을 저장하는 벡터로 인해 O(n)입니다.