크기가 N인 정수 배열이 주어졌을 때, 배열의 원소들로 구성할 수 있는 최대 곱 부분집합과 최소 곱 부분집합을 찾는 것이 이 글의 목표입니다. 이 문제는 두 개의 변수를 활용하면 효율적으로 해결할 수 있습니다. 하나는 지금까지 찾은 최소 곱을 저장하는 minProd, 다른 하나는 지금까지 찾은 최대 곱을 저장하는 maxProd입니다.
배열을 순회하는 동안에는 각 원소를 minProd와 maxProd에 곱해 보면서, 이전 최대 곱(prevMax)·이전 최소 곱(prevMin)·현재 최대 곱(curMax)·현재 최소 곱(curMin), 그리고 현재 원소 자체를 모두 비교해 값을 갱신합니다. 음수가 포함된 배열에서도 정확한 결과를 얻으려면 최댓값과 최솟값을 동시에 추적해야 하기 때문입니다.
입력 및 출력 예시 1
Arr[]= { 1,2,5,0,2 }
출력
Maximum Product: 20 Minimum Product: 0
설명 − 첫 번째 원소(1)로 maxProd와 minProd를 초기화한 뒤, 두 번째 원소부터 순회를 시작합니다.
Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1 Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1 Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0 Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0
배열에 0이 포함되어 있어 0을 포함하는 부분집합의 곱은 0이 되며, 나머지 원소({1, 2, 5, 2})만으로 최대 곱 20을 얻을 수 있습니다.
입력 및 출력 예시 2
Arr[]= { -1,2,-5,0,2 }
출력
Maximum Product: 20 Minimum Product: -20
설명 − 최대 곱은 음수 두 개(-1, -5)를 함께 포함해 부호를 상쇄하는 부분집합 { -1, 2, -5, 2 }에서 20이 됩니다.
반면 최소 곱은 음수를 홀수 개만 포함하는 부분집합 { 2, -5, 2 }에서 -20이 됩니다. 이처럼 음수의 개수에 따라 최적 부분집합이 달라지므로, 최댓값과 최솟값을 함께 관리하는 것이 중요합니다.
알고리즘 접근 방식
- 정수 배열 Arr[]에는 양수와 음수가 섞여 있으며, 변수 size에는 배열의 길이가 담깁니다.
- getProductSubset(int arr[], int n) 함수는 배열을 입력받아 원소들의 최대 곱과 최소 곱을 계산해 출력합니다.
- curMin, curMax 변수에는 현재까지 계산된 최소·최대 곱이 저장되며, 초기값은 arr[0]입니다.
- prevMin, prevMax 변수에는 바로 이전 단계의 최소·최대 곱이 저장되며, 초기값 역시 arr[0]입니다.
- maxProd와 minProd 변수에는 최종적인 최대·최소 곱이 저장됩니다.
- 배열의 두 번째 원소 arr[1]부터 마지막 인덱스까지 순회를 시작합니다.
- 최대 곱을 구할 때는 현재 원소 arr[i]를 prevMax와 prevMin에 각각 곱해 본 뒤, 여기에 arr[i] 자체와 기존 prevMax까지 포함해 네 값 중 가장 큰 것을 curMax에 저장합니다.
- curMax가 maxProd보다 크면 maxProd를 curMax로 갱신합니다.
- 다음 반복을 위해 prevMax를 curMax로 업데이트합니다.
- prevMin, curMin, minProd에 대해서도 비교 조건만 반대로 바꾸어 같은 과정을 수행합니다.
- 루프가 종료되면 maxProd와 minProd에 저장된 결과를 출력합니다.
C++ 구현 코드
#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
// 모든 곱 변수를 arr[0]으로 초기화
int curMax = arr[0];
int curMin = arr[0];
int prevMax = arr[0];
int prevMin= arr[0];
int maxProd = arr[0];
int minProd = arr[0];
int temp1=0,temp2=0,temp3=0;
// arr[0] 이후의 모든 원소 처리
for (int i = 1; i < n; ++i){
/* 현재 최대 곱은 다음 값들 중 최댓값이다
1) prevMax * arr[i] (arr[i]가 양수일 때 유리)
2) prevMin * arr[i] (arr[i]가 음수일 때 유리)
3) 현재 원소 arr[i]
4) 이전 최대 곱 prevMax */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1>temp2?temp1:temp2;
curMax = temp3>arr[i]?temp3:arr[i];
curMax = curMax>prevMax?curMax:prevMax;
/* 현재 최소 곱은 다음 값들 중 최솟값이다
1) prevMin * arr[i] (arr[i]가 양수일 때 유리)
2) prevMax * arr[i] (arr[i]가 음수일 때 유리)
3) 현재 원소 arr[i]
4) 이전 최소 곱 prevMin */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1<temp2?temp1:temp2;
curMin = temp3<arr[i]?temp3:arr[i];
curMin = curMin<prevMin?curMin:prevMin;
maxProd = maxProd>curMax?maxProd:curMax;
minProd = minProd<curMin?minProd:curMin;
// 현재 값을 다음 반복용 이전 값으로 복사
prevMax = curMax;
prevMin = curMin;
}
std::cout<<"Maximum Subset Product: "<<maxProd;
std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
// int arr[] = {-4, 1,1, 3, 5,7};
int size = 7;
getProductSubset(Arr,size ) ;
return 0;
}
실행 결과
Maximum Subset Product: 192 Minimum Subset Product: -64
위 실행 결과에서 최대 곱 192는 부분집합 { -4, -3, 2, 8 }의 곱이며, 최소 곱 -64는 음수를 하나만 포함하는 부분집합 { -4, 1, 2, 8, 1 }의 곱입니다.
정리
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(N)이며, 상수 개의 변수만 추가로 사용하므로 공간 복잡도는 O(1)입니다. 음수와 0이 섞인 배열에서도 최대·최소 곱 부분집합을 안정적으로 찾을 수 있다는 점이 이 접근 방식의 핵심입니다.