양수로만 이루어진 두 개의 배열 arr1과 arr2가 주어졌다고 가정해 보겠습니다. 두 배열에는 서로 동일한 개수의 값이 들어 있습니다.
우리가 작성해야 할 함수는 두 배열의 요소들을 짝지어 곱했을 때, 그 곱들의 합이 최대가 되도록 만드는 것입니다.
여기서 조건은 다음과 같습니다. arr1의 각 요소는 arr2의 정확히 하나의 요소와 곱해져야 하며, 그 반대도 마찬가지입니다. 즉, 두 배열의 모든 요소는 정확히 한 번씩만 사용되어야 하고, 이렇게 만들어진 곱들의 합이 최대가 되어야 합니다.
예를 들어 다음과 같은 배열이 있다고 해보겠습니다.
arr1 = [5,1,3,4,2]
arr2 = [8,10,9,7,6]
가능한 곱의 합 중 하나는 다음과 같습니다.
5*6 + 1*7 + 3*9 + 4*10 + 2*8
하지만 이 조합이 반드시 가장 큰 합이라고 볼 수는 없습니다.
접근 방식
곱의 합을 최대화하려면 정렬(Sort)을 활용하는 것이 가장 효과적입니다. 두 배열을 같은 방향(내림차순 또는 오름차순)으로 정렬한 뒤 같은 인덱스의 요소끼리 곱하면 곱의 합이 최대가 됩니다.
직관적으로 생각해 보면, 가장 큰 값끼리 곱하고 그다음으로 큰 값끼리 곱하는 방식이 임의로 섞어서 곱하는 경우보다 항상 더 크거나 같은 결과를 만들기 때문입니다.
예제 코드
다음은 위 접근 방식을 구현한 코드입니다.
const arr1 = [5,1,3,4,2];
const arr2 = [8,10,9,7,6];
const sorter = (a, b) => b - a;
const greatestProduct = (a1, a2) => {
if(a1.length !== a2.length){
return false;
};
const a1Sorted = a1.slice().sort(sorter);
const a2Sorted = a2.slice().sort(sorter);
let res = 0;
for(let i = 0; i < a1.length; i++){
res += (a1Sorted[i] * a2Sorted[i]);
};
return res;
};
console.log(greatestProduct(arr1, arr2));
코드 설명
- 먼저 두 배열의 길이가 같은지 확인하고, 다르면 false를 반환합니다.
slice()를 사용해 원본 배열을 변경하지 않고 복사한 뒤, 내림차순으로 정렬합니다.- 정렬된 두 배열의 같은 인덱스 요소들을 곱하여 결과값에 누적합니다.
- 모든 곱을 더한 최종 값을 반환합니다.
출력
콘솔에 출력되는 결과는 다음과 같습니다.
130
두 배열을 내림차순으로 정렬하면 arr1은 [5,4,3,2,1], arr2는 [10,9,8,7,6]이 되고, 5×10 + 4×9 + 3×8 + 2×7 + 1×6 = 130으로 최대 곱의 합을 얻을 수 있습니다.