이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어지며, 우리의 목표는 배열에서 만들 수 있는 최대 곱 부분집합(Maximum Product Subset)을 찾는 프로그램을 작성하는 것입니다.
문제 설명
배열 요소들 중 일부를 선택해 만든 부분집합의 곱 중 가장 큰 값을 계산해야 합니다.
부분집합(Subset)이란, 배열 sub[]의 모든 원소가 배열 arr[]에 포함되어 있을 때 sub[]를 arr[]의 부분집합이라고 합니다.
예제로 이해하기
입력
arr[] = {4, 5, 2, -1, 3}출력
40
설명
부분집합 sub[] = {4, 5, 2}
곱 = 4 * 5 * 2 = 40해결 접근 방법
1. 단순한 방법 (브루트 포스)
가장 직관적인 방법은 배열의 모든 가능한 부분집합을 생성하고, 각각의 곱을 계산한 뒤 그중 최댓값을 반환하는 것입니다.
구현은 간단하지만 중첩 반복문이 필요하여 시간 복잡도가 O(n² × n)에 달해 비효율적입니다.
2. 효율적인 방법
효율적인 해법은 배열을 한 번만 순회하면서 다음 두 가지 정보를 세는 것입니다.
- 음수의 개수(nofNeg)
- 0의 개수(nof0)
그런 다음 아래 조건에 따라 최대 곱(maxProd)을 결정합니다.
- 경우 1 (nof0 = 0이고 음수 개수가 짝수): 배열의 모든 원소를 곱합니다.
maxProd = arr[0] × arr[1] × … × arr[n-1] - 경우 2 (nof0 = 0이고 음수 개수가 홀수): 절댓값이 가장 작은 음수(0에 가장 가까운 음수) 하나를 제외한 나머지 원소들을 곱합니다.
- 경우 3 (nof0 ≠ 0): 곱셈에서 0을 모두 제외하고, 경우 1과 경우 2와 동일하게 처리합니다.
- 특수 경우: 0을 제외한 유일한 원소가 음수 하나뿐이라면 maxProd = 0입니다.
알고리즘
초기화
maxProd = 1;
1단계
배열을 순회하며 nof0(0의 개수)과 nofNeg(음수의 개수)를 세고, maxProd = maxProd * arr[i] (i는 0부터 n-1까지)
2단계
다음 경우를 고려합니다. 경우 1: if(nofNeg % 2 == 0) → maxProd 그대로 사용 경우 2: if(nofNeg % 2 != 0) → maxProd = maxProd / (절댓값이 가장 작은 음수) 경우 3: if(nof0 == (n-1) && nofNeg == 1) → maxProd = 0
3단계
maxProd 출력
C++ 구현 예제
아래 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.
#include <iostream>
using namespace std;
int findMaxSubsetProd(int arr[], int n){
int larNeg = -1000;
int nofNeg = 0, Nof0 = 0;
int maxProd = 1;
for (int i = 0; i < n; i++) {
if (arr[i] == 0){
Nof0++;
continue;
}
else if (arr[i] < 0) {
nofNeg++;
if(larNeg < arr[i])
larNeg = arr[i];
}
maxProd = maxProd * arr[i];
}
if(nofNeg % 2 == 0){
return maxProd;
}
else if(nofNeg % 2 != 0)
return (maxProd / larNeg);
if(Nof0 == (n-1) && nofNeg == 1)
return 0;
return maxProd;
}
int main(){
int arr[] = {4, -2, 5, -1, 3, -6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"배열의 최대 곱 부분집합 값은 "<<findMaxSubsetProd(arr, n);
return 0;
}출력
배열의 최대 곱 부분집합 값은 720
동작 원리 분석
예제 배열 {4, -2, 5, -1, 3, -6}에는 음수가 3개(-2, -1, -6) 있으므로 홀수 개입니다. 따라서 0에 가장 가까운 음수인 -1을 제외한 나머지 원소들의 곱을 계산합니다.
4 × (-2) × 5 × 3 × (-6) = 720이 되며, 이것이 만들 수 있는 최대 곱입니다.
시간 복잡도
이 알고리즘은 배열을 단 한 번 순회하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 상수 공간 O(1)만 사용합니다. 브루트 포스 방식의 O(2ⁿ) 또는 O(n²×n)에 비해 훨씬 효율적입니다.