문제 설명
정수 배열이 하나 주어졌을 때, 그중 세 개의 숫자를 골라 곱했을 때 가장 큰 값이 되는 경우를 찾고, 그 최대 곱을 반환하는 것이 목표입니다.
예를 들어 입력이 [1, 1, 2, 3, 3]이라면, 세 원소 [2, 3, 3]을 선택했을 때 곱이 18로 가장 크므로 출력은 18이 됩니다.
접근 방법
이 문제는 배열을 정렬한 뒤 두 가지 후보만 비교하면 간단히 해결할 수 있습니다.
- 배열 nums를 오름차순으로 정렬합니다.
- l := nums의 크기
- a := nums[l - 1], b := nums[l - 2], c := nums[l - 3] (가장 큰 세 수)
- d := nums[0], e := nums[1] (가장 작은 두 수)
- a × b × c 와 d × e × a 중 더 큰 값을 반환합니다.
왜 두 가지 경우를 비교할까요?
배열에 음수가 포함되어 있을 수 있기 때문입니다. 음수끼리 곱하면 양수가 되므로, 가장 작은 두 개의 음수(d, e)와 가장 큰 양수(a)를 곱한 값이 오히려 가장 큰 세 양수의 곱보다 커질 수 있습니다. 따라서 두 경우를 모두 계산해 최댓값을 선택해야 합니다.
구현 예제
다음 C++ 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int l = nums.size();
int a = nums[l - 1], b = nums[l - 2], c = nums[l - 3], d = nums[0], e = nums[1];
return max(a * b * c, d * e * a);
}
};
main(){
Solution ob;
vector<int> v = {1,1,2,3,3};
cout << (ob.maximumProduct(v));
}
입력
{1,1,2,3,3}출력
18
복잡도 분석
정렬에 O(n log n)의 시간이 소요되며, 나머지 연산은 상수 시간에 처리되므로 전체 시간 복잡도는 O(n log n), 공간 복잡도는 추가 메모리를 사용하지 않는 한 O(1)입니다.