이 문제에서는 n개의 정수로 구성된 배열 arr[]가 주어집니다. 우리의 과제는 이 배열에서 삼중항(triplet, 크기 3의 부분 수열)의 최대 곱을 찾아 그 값을 반환하는 것입니다. 즉, 모든 가능한 세 원소 조합 중에서 곱이 가장 큰 조합을 찾으면 됩니다.
예시를 통해 문제를 이해해 보겠습니다.
입력
arr[] = {9, 5, 2, 11, 7, 4}출력
693
설명
배열의 모든 원소 중에서 가장 큰 곱을 만들어내는 삼중항을 찾습니다.
maxProd = 9 * 11 * 7 = 693
해결 접근 방법
이 문제는 여러 가지 방법으로 해결할 수 있습니다. 아래에서 대표적인 세 가지 방법을 살펴보겠습니다.
방법 1: 브루트 포스(완전 탐색)
가장 직관적인 방법으로, 세 개의 중첩 반복문을 사용하여 배열에서 만들 수 있는 모든 삼중항 조합을 탐색합니다. 각 조합의 곱을 계산하고, 그중 최댓값을 반환합니다.
알고리즘
초기화
maxProd = −1000
1단계:
세 개의 중첩 루프 생성: Loop 1: i → 0부터 n−3까지 Loop 2: j → i+1부터 n−2까지 Loop 3: k → j+1부터 n−1까지
1.1단계 −
곱 계산: prod = arr[i] * arr[j] * arr[k]
1.2단계 −
if prod > maxProd → maxProd = prod
3단계 −
return maxProd
구현 예제
위 해결 방법을 구현한 프로그램입니다.
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int maxProd = −1000;
int prod;
for (int i = 0; i < n − 2; i++)
for (int j = i + 1; j < n − 1; j++)
for (int k = j + 1; k < n; k++){
prod = arr[i] * arr[j] * arr[k];
if(maxProd < prod)
maxProd = prod;
}
return maxProd;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열에서 삼중항의 최대 곱은 "<<calcMaxProd(arr, n);
return 0;
}출력
배열에서 삼중항의 최대 곱은 693
이 방법은 구현이 간단하지만 시간 복잡도가 O(n³)으로, 배열의 크기가 커지면 비효율적이라는 단점이 있습니다.
방법 2: 정렬 활용
배열을 내림차순으로 정렬하면 최대 곱을 만드는 삼중항은 다음 두 경우 중 하나에 속합니다.
(arr[0], arr[1], arr[2]) → 가장 큰 세 수의 조합 (arr[0], arr[n−1], arr[n−2]) → 가장 큰 수와 가장 작은 두 수의 조합
두 번째 조합이 필요한 이유는 음수가 포함된 경우입니다. 음수 두 개를 곱하면 양수가 되므로, 가장 작은 음수 두 개와 가장 큰 양수의 조합이 최댓값이 될 수 있습니다. 따라서 두 조합의 곱 중 더 큰 값을 반환하면 됩니다.
알고리즘
1단계 −
주어진 배열을 내림차순으로 정렬합니다.
2단계 −
두 삼중항의 곱을 계산합니다. maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]
3단계 −
if(maxTriplet1 > maxTriplet2) → return maxTriplet1
4단계 −
else → return maxTriplet2
구현 예제
위 해결 방법의 동작을 보여주는 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int calcMaxProd(int arr[], int n){
sort(arr, arr + n, greater<>());
int maxTriplet1 = arr[0]*arr[1]*arr[2];
int maxTriplet2 = arr[0]*arr[n−1]*arr[n−2];
if(maxTriplet1 > maxTriplet2)
return maxTriplet1;
return maxTriplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열에서 삼중항의 최대 곱은 "
<<calcMaxProd(arr, n);
return 0;
}출력
배열에서 삼중항의 최대 곱은 693
정렬 기반 방법의 시간 복잡도는 O(n log n)으로, 완전 탐색보다 효율적입니다.
방법 3: 핵심 값만 추출하기 (선형 시간)
최대 곱을 만드는 삼중항은 앞서 설명한 것처럼 다음 두 조합 중 하나임을 알 수 있습니다.
(최댓값, 두 번째 최댓값, 세 번째 최댓값) (최댓값, 최솟값, 두 번째 최솟값)
따라서 배열을 한 번만 순회하면서 이 다섯 개의 값만 찾으면, 정렬 없이도 O(n) 시간에 답을 구할 수 있습니다.
알고리즘
초기화
max = −1000, secMax = −1000, thirdMax = −1000, min = 10000, secMin = 10000
1단계 −
배열을 순회합니다: i → 0부터 n−1까지
1.1단계
if(arr[i] > max) → thirdMax = secMax, secMax = max, max = arr[i]
1.2단계 −
elseif(arr[i] > secMax) → thirdMax = secMax, secMax = arr[i]
1.3단계 −
elseif(arr[i] > thirdMax) → thirdMax = arr[i]
1.4단계 −
if(arr[i] < min) → secMin = min, min = arr[i]
1.5단계 −
elseif(arr[i] < secMin) → secMin = arr[i]
2단계 −
triplet1 = max * secMax * thirdMax triplet2 = max * min * secMin
3단계 −
if(triplet1 > triplet2) → return triplet1
4단계 −
else → return triplet2
구현 예제
위 해결 방법의 동작을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int max = −1000, secMax = −1000, thirdMax = −1000;
int min = 1000, secMin = 1000;
for (int i = 0; i < n; i++){
if (arr[i] > max){
thirdMax = secMax;
secMax = max;
max = arr[i];
}
else if (arr[i] > secMax){
thirdMax = secMax;
secMax = arr[i];
}
else if (arr[i] > thirdMax)
thirdMax = arr[i];
if (arr[i] < min){
secMin = min;
min = arr[i];
}
else if(arr[i] < secMin)
secMin = arr[i];
}
int triplet1 = max * secMax * thirdMax;
int triplet2 = max * secMin * min;
if(triplet1 > triplet2)
return triplet1;
return triplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열에서 삼중항의 최대 곱은 "
<<calcMaxProd(arr, n);
return 0;
}출력
배열에서 삼중항의 최대 곱은 693
마무리 및 성능 비교
세 가지 방법의 시간 복잡도를 비교하면 다음과 같습니다.
방법 1 (브루트 포스): O(n³) — 구현이 간단하지만 대규모 입력에는 부적합합니다.
방법 2 (정렬): O(n log n) — 코드가 간결하고 실용적입니다.
방법 3 (선형 순회): O(n) — 단 한 번의 순회로 최적의 성능을 보이며, 공간 복잡도도 O(1)입니다.
실무에서는 방법 3이 가장 효율적이지만, 면접이나 학습 목적으로는 세 가지 방법을 모두 이해하는 것이 좋습니다. 특히 음수가 포함된 배열에서 두 개의 음수 곱이 양수가 되는 경우를 고려해야 한다는 점이 이 문제의 핵심 포인트입니다.