C++ 배열 최대 곱 구하기: 모든 반복 요소의 빈도 합이 2 × k 이하가 되도록

이 튜토리얼에서는 배열에 포함된 요소들의 곱 중 최댓값을 구하는 프로그램을 C++로 작성해 보겠습니다. 여기서 중요한 조건은, 곱에 사용된 모든 반복 요소의 빈도 합이 2 × k보다 작거나 같아야 한다는 점입니다.

즉, 하나의 배열과 정수 k가 주어졌을 때, 각 숫자의 등장 횟수(빈도)의 총합이 2 × k 이하가 되도록 요소를 선택하면서 얻을 수 있는 최대 곱을 찾아야 합니다.

접근 방법

이 문제는 정렬과 해시 맵(unordered_map)을 활용하면 효율적으로 해결할 수 있습니다. 전체적인 흐름은 다음과 같습니다.

정렬: 배열을 오름차순으로 정렬하여 큰 값부터 우선적으로 처리할 수 있게 준비합니다.
고유 요소 곱하기: 해시 맵에 각 요소의 등장 횟수를 기록하면서, 처음 등장한 요소들만 곱에 포함시킵니다.
반복 요소 추가: 큰 값부터 역순으로 탐색하며, 남은 k 예산 범위 내에서 반복 요소를 추가로 곱해 결과를 극대화합니다.
k가 모두 소진되면 탐색을 종료하고 최종 곱을 반환합니다.

C++ 구현 예시

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

// 최대 곱 값을 반환하는 함수
ll maxProd(int arr[], int n, int k) {
    ll product = 1;
    unordered_map<int, int> s;
    sort(arr, arr + n);
    // 고유한 요소를 곱에 포함하고 빈도를 해시 맵에 저장
    for (int i = 0; i < n; i++) {
        if (s[arr[i]] == 0) {
            product = product * arr[i];
        }
        s[arr[i]] = s[arr[i]] + 1;
    }
    // 큰 값부터 반복 요소를 추가로 곱함
    for (int j = n - 1; j >= 0 && k > 0; j--) {
        if ((k > (s[arr[j]] - 1)) && ((s[arr[j]] - 1) > 0)) {
            product *= pow(arr[j], s[arr[j]] - 1);
            k = k - s[arr[j]] + 1;
            s[arr[j]] = 0;
        }
        if (k <= (s[arr[j]] - 1) && ((s[arr[j]] - 1) > 0)) {
            product *= pow(arr[j], k);
            break;
        }
    }
    return product;
}

int main() {
    int arr[] = { 5, 6, 7, 8, 2, 5, 6, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxProd(arr, n, k);
    return 0;
}

실행 결과

동작 원리 살펴보기

예제 배열 {5, 6, 7, 8, 2, 5, 6, 8}을 정렬하면 {2, 5, 5, 6, 6, 7, 8, 8}이 됩니다. 첫 번째 반복문에서 고유한 값인 2, 5, 6, 7, 8을 한 번씩 곱해 초기 곱 3360을 만듭니다.

이후 두 번째 반복문에서는 큰 값부터 남은 k(=2)를 사용해 반복 요소를 추가합니다. 먼저 8을 한 번 더 곱해(k 1 소진) 26880이 되고, 다음으로 6을 한 번 더 곱해(k 1 소진) 최종 결과인 161280(= 2 × 5 × 6 × 6 × 7 × 8 × 8)을 얻습니다.

마무리

이처럼 정렬과 해시 맵을 조합하면 빈도 제약 조건이 있는 최대 곱 문제를 O(n log n) 시간 복잡도로 해결할 수 있습니다. 배열의 크기가 커지더라도 안정적으로 동작하므로, 코딩 테스트 준비나 알고리즘 학습에 유용하게 활용할 수 있습니다.