[Javascript] 배열의 조합 구하기

알고리즘 문제를 접하다 보면, 간혹 배열의 조합을 구한 후 추가 계산을 해야 하는 문제가 있다.

조합하는 원소의 개수가 2개라면 두번의 for 문으로 해결이 가능하지만, 3개 이상은 구현하는데 깔끔하지 않기도 하지만

배열 길이에 따라서 속도가 엄청나게 느려질 수 있기 때문에, 다른 방법을 사용해야 한다.

 

Python의 경우, 조합과 관련된 내장 함수가 있어서 구하기 쉽지만

Javascript는 관련 함수가 없어서 직접 구현 해야 한다.

 

// 배열에서 n개를 골라 조합하기 

function combinations(arr, n){
        const results = []; // 반환할 최종 함수
        
        if (n === 1){
        	// 추가해야할 원소가 1개 남으면, 배열 내 모든 원소들 배열 형태로 반환
            return arr.map((value) => [value]);
        };
        
        arr.forEach((current, index, origin_array) => {
            const rest_arr = origin_array.slice(index + 1); // current 값 제외 나머지 별도 리스트 저장
            const comb = combinations(rest_arr, n - 1); // 위의 리스트 받아서, 자기 자신 함수(재귀) 호출
            const attach_arry = comb.map((comb_value) => [current, ...comb_value]); // 위의 반환값 + current => 새로운 배열로 변환
            
            results.push(...attach_arry); // 신규 배열 result 추가
        });
        
        return results;
    }

재귀 함수는 종료 조건을 만나기 전 까지 자기 자신을 계속해서 호출하기 때문에 이해하기가 어렵다.

일반적인 경우를 가정하면 헷갈릴 가능성이 있으므로 가능한 작은 케이스를 가정하고 하나의 분기에 집중해야 한다.

// 배열에서 n개를 골라 조합하기 

function combinations(arr, n){
        const results = [];
        
        if (n === 1){
            return arr.map((value) => [value]);
        };
        
        arr.forEach((current, index, origin_array) => {
            const rest_arr = origin_array.slice(index + 1); 
            const comb = combinations(rest_arr, n - 1); 
            const attach_arry = comb.map((comb_value) => [current, ...comb_value]);
            
            results.push(...attach_arry);
        });
        
        return results;
    }

여기서는 [1, 2, 3, 4] 의 배열에서 3개의 원소를 골라 조합하는 것을 가정하고 설명하겠다.

 

첫 배열이 들어가면, 1을 제외한 나머지 배열 [2, 3, 4] 를

다시 자기 자신인 combinations 함수를 호출하여 넣는다 (const comb 라인)

 

최초 기준으로 const comb = combinations(rest_arr, n - 1); 의 라인으로 인해

배열 [2, 3, 4] 가 다시 들어왔고, 조합해야 하는 숫자 개수 n은 하나 줄어 2로 되었다.

 

n 조건을 만족하지 못하므로 아래로 내려와 첫 원소인 2, index 0이 기록된다.

rest_arr은 2를 제외한 [3, 4]가 되며, 이를 다시 combinations 함수를 호출하여 넣는다 ( const comb ~ 라인)

 

이번에는 n 이 1이므로, 종료 조건을 만족했다. 따라서 이전 과정과는 다르게

배열의 각 원소들을 개별 배열로 변환하여 반환한다.

 

이제 첫 번째 1을 두고, 두 번째 2를 두고 온 배열에서 더 이상의 combinations 함수를 수행할 일은 없으므로

이제 const comb ~ 라인 이후가 시작된다.

2회차 ( current 를 2로 가지고 있는 회차) 에서의 comb 값은 [[3], [4]] 로 반환되었다.

map method를 이용해 각 각의 원소들 ([3], [4])을 배열 해제 한 후 기존 값 (current, 현재 : 2)과 묶어 새로운 배열로 만든다.

또한 result로 그대로 push 하게되면 배열 > 배열 > 배열 의 구조가 되므로, 한 단계 풀어서 push 한다.

 

이제, forEach의 모든 연산을 완료했으므로, results 를 return 한다.

이 return 값([ [2, 3], [2, 4] ])은 current 값이 1, index 값은 0이었던

최초의 함수 진행에서 combinations([2, 3, 4], n-1)의 값과 같다.

이 과정을 거치면 current가 2였던 결과물과 함산하게 되어 [1,2,3], [1,2,4]가 추가된다.

[1, 2, 3, 4]에서 1이 포함된 조합의 개수는 3개([1, 2, 3], [1, 2, 4], [1, 3, 4])인데, 현재 예시에는 [1, 3, 4] 가 없다.

그 과정은 위의 내용을 토대로 추측해보길 바란다.

 

과정에 대한 힌트는 아래 참고.