JavaScript에서 숫자 배열을 평균이 같은 두 그룹으로 나누는 방법

문제 소개

정수로 이루어진 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 입력 배열의 요소들을 두 그룹으로 나누었을 때(두 그룹의 요소 개수는 같아도 되고 달라도 됩니다), 두 그룹의 평균이 정확히 동일해지는 조합이 존재하는지 판별해야 합니다. 만약 그러한 조합이 존재하면 true를 반환하고, 존재하지 않으면 false를 반환해야 합니다.

예시

입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [6, 3, 2, 8, 1, 5, 7, 4];

이때 기대되는 출력은 다음과 같습니다.

const output = true;

그 이유는 배열을 [8, 1, 5, 4]와 [6, 3, 2, 7] 두 그룹으로 나눌 수 있고, 두 그룹 모두 평균이 4.5로 동일하기 때문입니다.

접근 방법: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 배열 전체의 합을 구합니다.
2차원 DP 테이블을 만들어, k개의 요소를 선택했을 때 합이 j가 될 수 있는지 여부를 저장합니다.
각 요소를 순회하면서 가능한 부분 집합의 합과 개수를 갱신하고, 현재 선택된 부분 집합과 나머지 요소들의 평균이 일치하는지 검사합니다.

평균 비교 시에는 실수 연산 대신 교차 곱셈 방식인 (부분집합의 합) × (나머지 개수) == (나머지의 합) × (부분집합 개수) 조건을 사용하여 부동 소수점 오류 없이 정확하게 비교할 수 있습니다.

코드 구현

다음은 위 접근 방식을 구현한 코드입니다.

const arr = [6, 3, 2, 8, 1, 5, 7, 4];
const canHaveEqualAveragePartition = (arr = []) => {
    const sum = arr.reduce((acc, val) => acc + val);
    const array = Array(sum+1).fill(false).map(() =>
    Array(arr.length+1).fill(false));
    array[0][0] = true;
    for(let i=0; i < arr.length; ++i){
        for(let j=sum - arr[i];j>=0;--j){
            for(let k=arr.length-2;k>=0;--k){
                if(array[j][k]){
                    array[j + arr[i]][k+1] = true;
                    if((j + arr[i]) * (arr.length - k - 1) == (sum - j -arr[i]) * (k + 1)){
                        return true;
                    }
                }
            }
        }
    }
    return false;
};
console.log(canHaveEqualAveragePartition(arr));

코드 설명

sum 계산: reduce() 메서드로 배열 전체의 합을 구합니다.
DP 테이블 초기화: 크기가 (sum+1) × (length+1)인 2차원 불리언 배열을 생성하고, 아무것도 선택하지 않은 상태인 array[0][0]만 true로 설정합니다.
상태 갱신: 각 요소를 역순으로 순회하며, 기존에 도달 가능한 상태에 현재 요소를 추가한 새로운 상태(합, 개수)를 표시합니다.
평균 일치 검사: 새로운 상태가 만들어질 때마다 교차 곱셈 조건으로 두 그룹의 평균이 같은지 확인하고, 일치하면 즉시 true를 반환합니다.

출력 결과

콘솔 출력 결과는 다음과 같습니다.

true

이처럼 동적 계획법을 활용하면 모든 분할 조합을 일일이 시도하는 브루트 포스 방식보다 훨씬 효율적으로 문제를 해결할 수 있습니다.