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

C++ 알고리즘 풀이: 팀의 최대 성능 구하기

문제 설명

n명의 엔지니어가 있다고 가정해 보겠습니다. 각 엔지니어에게는 1부터 n까지 번호가 매겨져 있으며, 두 개의 배열 speed와 efficiency가 주어집니다. 여기서 speed[i]와 efficiency[i]는 각각 i번째 엔지니어의 속도와 효율을 나타냅니다.

목표는 최대 k명의 엔지니어로 구성된 팀의 최대 성능(maximum performance)을 구하는 것입니다. 계산 결과가 매우 커질 수 있으므로, 답은 10^9 + 7로 나눈 나머지(modulo)로 반환해야 합니다.

여기서 팀의 성능은 다음 공식으로 정의됩니다.

팀의 성능 = 팀원 전체의 속도 합 × 팀원 중 최소 효율

예시 입력과 출력

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

  • n = 6
  • speed = [1, 5, 8, 2, 10, 3]
  • efficiency = [9, 7, 2, 5, 4, 3]
  • k = 2

이 경우 출력은 60입니다. 속도가 10이고 효율이 4인 엔지니어와, 속도가 5이고 효율이 7인 엔지니어를 선택했을 때 팀의 성능이 최대가 되기 때문입니다.

성능 = (10 + 5) × min(4, 7) = 15 × 4 = 60

문제 해결 접근 방법

이 문제는 내림차순 정렬과 최소 힙(min-heap) 기반 우선순위 큐를 함께 사용하면 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 팀의 성능은 팀원 중 최소 효율에 의해 결정되므로, 엔지니어를 효율 기준으로 내림차순 정렬한 뒤 차례대로 살펴보면, 현재 처리 중인 엔지니어의 효율이 곧 지금까지 고려한 후보군의 최소 효율이 됩니다. 이 상태에서 성능을 극대화하려면 속도의 합이 최대가 되어야 하므로, 우선순위 큐를 이용해 속도가 가장 낮은 팀원을 제거하면서 팀 인원을 k명 이하로 유지합니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  1. 결괏값 ret := 0으로 초기화합니다.
  2. (효율, 속도) 쌍을 저장할 2차원 배열 v를 정의하고, 모든 엔지니어를 {e[i], s[i]} 형태로 삽입합니다.
  3. 배열 v를 내림차순으로 정렬합니다.
  4. 최소 힙 기반 우선순위 큐 pq를 선언하고, 누적 속도 합 sum := 0으로 초기화합니다.
  5. i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
    • pq의 크기가 k와 같다면, sum에서 pq의 최상단 원소(현재 팀에서 가장 작은 속도)를 빼고 그 원소를 제거합니다.
    • sum에 v[i]의 속도(v[i][1])를 더한 뒤, v[i][1]을 pq에 삽입합니다.
    • ret을 ret과 sum × v[i][0] 중 더 큰 값으로 갱신합니다.
  6. ret mod (10^9 + 7)을 반환합니다.

C++ 구현 코드

아래 구현 예제를 통해 동작 방식을 더 자세히 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int maxPerformance(int n, vector<int>& s, vector<int>& e, int k){
        long long int ret = 0;
        vector<vector<int> > v;
        for (int i = 0; i < n; i++) {
            v.push_back({ e[i], s[i] });
        }
        sort(v.rbegin(), v.rend());
        priority_queue<int, vector<int>, greater<int> > pq;
        long long int sum = 0;
        for (int i = 0; i < n; i++) {
            if (pq.size() == k) {
                sum -= pq.top();
                pq.pop();
            }
            sum += v[i][1];
            pq.push(v[i][1]);
            ret = max(ret, sum * v[i][0]);
        }
        return ret % (long long int)(1e9 + 7);
    }
};
main(){
    Solution ob;
    vector<int> v = {1,5,8,2,10,3};
    vector<int> v1 = {9,7,2,5,4,3};
    cout << (ob.maxPerformance(6,v,v1,2));
}

입력

6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2

출력

60

복잡도 분석

엔지니어 배열을 정렬하는 데 O(n log n)의 시간이 걸리고, 이후 각 엔지니어에 대해 우선순위 큐 연산(O(log k))을 수행하므로 전체 시간 복잡도는 O(n log n)입니다. 추가로 사용되는 공간은 정렬된 배열과 우선순위 큐를 위해 O(n)입니다.