문제 정의
두 개의 숫자 배열 arr1과 arr2를 각각 첫 번째, 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
두 배열에 담긴 요소들의 합은 서로 다릅니다. 함수는 첫 번째 배열에서 한 요소를 골라 두 번째 배열로 옮기고, 동시에 두 번째 배열에서 한 요소를 골라 첫 번째 배열로 옮겨서 두 배열의 합이 서로 같아지도록 만들어야 합니다. 최종적으로 이렇게 교환된 두 요소를 배열 형태로 반환하면 됩니다.
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const arr1 = [1, 2, 5];
const arr2 = [2, 4];
출력
const output = [5, 4];
출력 설명
arr1에서 5를 빼내 arr2에 추가하고, arr2에서 4를 빼내 arr1에 추가하면 두 배열의 합이 모두 7로 같아지기 때문입니다.
접근 방식
모든 조합을 일일이 시도하는 무차별 대입 방식도 가능하지만, 간단한 수학적 관계를 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다.
arr1의 요소 x와 arr2의 요소 y를 서로 교환한 뒤 두 배열의 합이 같아지려면 다음 식이 성립해야 합니다.
sumA - x + y = sumB - y + x
이 식을 정리하면 y = x + (sumB - sumA) / 2가 됩니다. 즉, arr1의 각 요소마다 목표가 되는 값을 하나씩 계산한 뒤, 그 값이 arr2에 존재하는지만 확인하면 됩니다. 존재 여부는 해시 객체(맵)를 사용하면 상수 시간에 확인할 수 있으므로 전체 시간 복잡도는 O(n + m)으로 줄어듭니다.
참고로 두 배열 합의 총합이 홀수라면 어떤 요소를 교환해도 합을 같게 만들 수 없으므로, 이 경우에는 빈 배열이 반환됩니다.
예제 코드
const arr1 = [1, 2, 5];
const arr2 = [2, 4];
const balanceArrays = (arr1 = [], arr2 = []) => {
const sumA = arr1.reduce((acc, v) => acc + v, 0);
const sumB = arr2.reduce((acc, v) => acc + v, 0);
const difference = (sumA + sumB) / 2 - sumA;
const map = arr2.reduce((acc, v) => {
acc[v] = true;
return acc;
}, {});
for (let i = 0; i < arr1.length; i++) {
if (map[arr1[i] + difference] === true) {
return [arr1[i], arr1[i] + difference];
}
}
return [];
};
console.log(balanceArrays(arr1, arr2));
코드 설명
reduce()를 사용해 두 배열의 합sumA와sumB를 각각 구합니다.difference는(sumA + sumB) / 2 - sumA로 계산되며, 이는(sumB - sumA) / 2와 같습니다. 교환 후 두 배열의 합이 같아지려면arr1의 요소에 이 값을 더한 숫자가 반드시arr2안에 존재해야 합니다.arr2의 모든 요소를 객체(맵)에 미리 저장해 두면 특정 값의 존재 여부를 O(1) 시간에 확인할 수 있습니다.arr1을 순회하면서현재 요소 + difference가 맵에 존재하면 해당 두 요소를 배열로 묶어 바로 반환합니다.- 끝까지 조건을 만족하는 쌍을 찾지 못하면 빈 배열
[]을 반환합니다.
실행 결과
[5, 4]