이 튜토리얼에서는 정수 배열이 주어졌을 때, 그 배열에서 서로 다른 세 개의 원소(크기 3의 부분 수열)를 선택하여 만들 수 있는 최대 곱을 구하는 방법을 다룹니다.
예를 들어 배열이 {10, 3, 5, 6, 20}이라면, 세 원소 10, 6, 20을 곱한 1200이 최대 곱이 됩니다.
접근 방법: 완전 탐색(Brute Force)
가장 직관적인 방법은 배열에서 가능한 모든 세 원소 조합을 확인하는 것입니다. 세 개의 중첩 반복문을 사용해 인덱스 i < j < k를 순회하며 각 조합의 곱을 계산하고, 그중 최댓값을 저장하면 됩니다. 이 방법의 시간 복잡도는 O(n³)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 최대 곱을 찾는 함수
int maxProduct(int arr[], int n) {
// 원소가 3개 미만이면 트리플렛을 만들 수 없음
if (n < 3)
return -1;
int max_product = INT_MIN;
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++)
max_product = max(max_product, arr[i] * arr[j] * arr[k]);
return max_product;
}
int main() {
int arr[] = { 10, 3, 5, 6, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
int result = maxProduct(arr, n);
if (result == -1)
cout << "트리플렛이 존재하지 않습니다";
else
cout << "최대 곱은 " << result;
return 0;
}실행 결과
최대 곱은 1200
코드 설명
- 예외 처리: 배열의 크기가 3보다 작으면 세 원소를 고를 수 없으므로 -1을 반환합니다.
- 초기값 설정: 최댓값 변수를
INT_MIN으로 초기화하여 음수가 포함된 경우에도 올바르게 동작합니다. - 삼중 반복문: 가능한 모든 (i, j, k) 조합에 대해 곱을 계산하고, 지금까지의 최댓값과 비교하여 갱신합니다.
더 효율적인 접근 방법
완전 탐색은 이해하기 쉽지만, 배열의 크기가 커지면 성능이 급격히 저하됩니다. 다음과 같은 개선 방법을 고려할 수 있습니다.
1. 정렬 활용 — O(n log n)
배열을 오름차순으로 정렬한 뒤, 아래 두 값 중 더 큰 것을 답으로 선택하면 됩니다.
- 가장 큰 세 수의 곱:
arr[n-1] × arr[n-2] × arr[n-3] - 가장 작은 두 수(음수일 수 있음)와 가장 큰 수의 곱:
arr[0] × arr[1] × arr[n-1]
음수끼리 곱하면 양수가 되므로, 가장 작은 두 수가 음수일 경우 두 번째 조합이 최댓값이 될 수 있습니다.
2. 한 번의 순회 — O(n)
배열을 한 번만 순회하면서 최댓값 1개, 두 번째·세 번째로 큰 값, 그리고 최솟값 1개, 두 번째로 작은 값을 함께 추적하면 정렬 없이도 선형 시간에 해를 구할 수 있습니다.
마무리
이번 글에서는 삼중 반복문을 이용한 완전 탐색 방식으로 배열에서 세 원소의 최대 곱을 구하는 방법을 살펴보았습니다. 면접이나 코딩 테스트에서는 정렬 기반 O(n log n) 또는 선형 O(n) 풀이를 함께 언급할 수 있다면 좋은 인상을 줄 수 있습니다.