정수로 이루어진 크기 n의 배열이 주어졌을 때, 배열에서 네 개의 원소를 선택하여 얻을 수 있는 곱의 최댓값을 구하는 문제입니다. 예를 들어 배열이 [3, 5, 20, 6, 10]이라면, 10 × 5 × 6 × 20 = 6000이 최대 곱이 됩니다.
해결 접근 방법
배열에 음수가 포함될 수 있기 때문에 단순히 가장 큰 네 수만 곱하는 것은 정답이 아닐 수 있습니다. 작은 음수 두 개를 곱하면 큰 양수가 되기 때문입니다. 따라서 다음 단계로 문제를 해결합니다.
- 배열을 오름차순으로 정렬합니다.
- x: 마지막(가장 큰) 네 원소의 곱
- y: 처음(가장 작은) 네 원소의 곱
- z: 처음 두 원소와 마지막 두 원소의 곱
- 세 값 x, y, z 중 최댓값을 반환합니다.
이 방법은 세 가지 경우를 모두 고려합니다. 모든 원소가 양수라면 마지막 네 원소의 곱이 최대이고, 음수가 섞여 있다면 절댓값이 큰 음수 두 개와 양수 두 개의 조합이, 혹은 모든 원소가 음수라면 처음 네 원소의 곱이 최대가 될 수 있습니다.
예제 코드
#include<iostream>
#include<algorithm>
using namespace std;
int maxQuadProduct(int arr[], int n) {
if (n < 4)
return -1;
sort(arr, arr + n);
int last_four = arr[n - 1] * arr[n - 2] * arr[n - 3] * arr[n - 4];
int first_four = arr[0] * arr[1] * arr[2] * arr[3];
int two_first_last = arr[0] * arr[1] * arr[n - 1] * arr[n - 2];
return max(last_four, max(first_four, two_first_last));
}
int main() {
int arr[] = { -10, -3, 5, 6, -20 };
int n = sizeof(arr) / sizeof(arr[0]);
int maximum_val = maxQuadProduct(arr, n);
if (maximum_val == -1)
cout << "No Quadruple Exists";
else
cout << "Maximum product is " << maximum_val;
}위 코드는 배열에 원소가 4개 미만이면 쿼드러플을 만들 수 없으므로 -1을 반환하고, 그렇지 않으면 정렬 후 세 가지 조합의 곱을 비교하여 최댓값을 출력합니다.
출력 결과
Maximum product is 6000
시간 복잡도는 정렬에 의해 지배되므로 O(n log n)이며, 공간 복잡도는 O(1)로 매우 효율적입니다. 브루트 포스 방식(O(n⁴))으로 네 수를 모두 조합해 보는 것보다 훨씬 빠른 성능을 제공합니다.