C++로 배열의 최대 곱 부분 집합 구하기

개요

이 튜토리얼에서는 C++를 사용하여 배열에서 최대 곱을 가지는 부분 집합(subset)을 찾는 프로그램을 구현하는 방법을 살펴보겠습니다.

양수와 음수 값이 함께 포함된 배열이 주어졌을 때, 배열의 요소 중 일부를 선택해 만들 수 있는 부분 집합의 곱 중 최댓값을 구하는 것이 목표입니다.

문제 해결 접근 방법

이 문제는 배열을 한 번만 순회하면서 선형 시간 안에 해결할 수 있습니다. 핵심 규칙은 다음과 같습니다.

• 0은 제외: 0을 곱하면 전체 곱이 0이 되므로 결과에 아무런 도움이 되지 않습니다.
• 음수 개수가 짝수: 모든 음수를 포함해도 곱은 양수가 되므로 그대로 사용합니다.
• 음수 개수가 홀수: 곱이 음수가 되지 않도록 절댓값이 가장 작은 음수(즉, 음수 중 최댓값) 하나를 제외합니다.
• 모든 요소가 0: 이 경우 만들 수 있는 최대 곱은 0입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int maxProductSubset(int a[], int n) {
    if (n == 1)
        return a[0];
    int max_neg = INT_MIN;
    int count_neg = 0, count_zero = 0;
    int prod = 1;
    for (int i = 0; i < n; i++) {
        // 0을 곱하는 것은 의미가 없음
        if (a[i] == 0) {
            count_zero++;
            continue;
        }
        if (a[i] < 0) {
            count_neg++;
            max_neg = max(max_neg, a[i]);
        }
        prod = prod * a[i];
    }
    if (count_zero == n)
        return 0;
    if (count_neg & 1) {
        if (count_neg == 1 &&
            count_zero > 0 &&
            count_zero + count_neg == n)
            return 0;
        prod = prod / max_neg;
    }
    return prod;
}
int main() {
    int a[] = { -1, -1, -2, 4, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << maxProductSubset(a, n);
    return 0;
}

출력

24

코드 설명

주어진 배열 {-1, -1, -2, 4, 3}에는 음수가 세 개(-1, -1, -2), 양수가 두 개(4, 3) 포함되어 있습니다.

1. 먼저 0이 없으므로 모든 요소를 곱하면 (-1) × (-1) × (-2) × 4 × 3 = -24가 됩니다.
2. 음수의 개수가 홀수(3개)이므로, 음수 중 최댓값인 -1을 제외해야 곱이 양수가 됩니다.
3. -24 ÷ (-1) = 24가 되어 최종적으로 최대 곱 24를 얻습니다.

특별히 주목할 부분은 음수가 하나뿐이고 나머지가 모두 0인 경우입니다. 이때는 어떤 부분 집합을 선택해도 곱이 0 또는 음수가 되므로 프로그램은 0을 반환합니다.

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
• 공간 복잡도: O(1) — 추가적인 저장 공간이 거의 필요하지 않습니다.