[ 자바스크립트(JavaScript) ] section08 - 15 - 수들의 조합

📍 section08 - 15 - 수들의 조합

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개인지 출력하는 문제다. 예를 들면, 5개의 숫자 arr=[2, 4, 5, 8, 12]로 주어지면 3를 뽑는 조합의 합이 6의 배수인 값은 [2, 4, 12] (18), [ 4, 8, 12 ] (24)로 총 2개가 있다.

 

이 문제를 풀기 위해선 n개의 정수를 뽑는 모든 경우의 수(조합)를 구하고, 조합의 합을 m으로 나눈 나머지가 0인 값을 찾으면 된다. 조합을 구현하는 방법은 다음을 참고하자.

 

내가 문제를 풀 때는 DFS함수에 인자를 L, s만 넘기고 L===k일 때 reduce 함수를 이용하여 더했는데, 그것보단 DFS에 sum 인자를 하나 더 넘겨서 L이 올라갈 때마다 현재 값을 더해주는 방법을 사용하는 것이 시간 복잡도를 단축시킬 수 있다. 이것과 궁금해서 선생님께 질문을 남겼는데 친절하게 답변해주셨다.

 

 

또한, 조합을 통해 뽑은 값을 보고 싶다면 `k`만큼 빈 배열을 선언해서 `temp[L] = arr[i]`로 확인해주면 된다.

 

여담으로 부분집합, 순열, 조합이 헷갈릴 때가 있었는데, 나름 기준을 세워서 구별하고 있다.

 

1. 부분집합: 1부터 N까지 값을 모두 포함하거나, 한개씩만 포함하거나, 일부만 포함하는 계산이 필요할 때

2. 순열: 일렬로 나열할 때 (뒤집은것은 취급한다.)

3. 조합: 뽑는 방법의 수 (뒤집은것은 취급하지 않는다.)

 

728x90

 

let n = 5;
let k = 3;
let arr = [2, 4, 5, 8, 12];
let m = 6;

console.log(solution(n, k, arr, m));

function solution(n, k, arr, m){
    let cnt = 0;
    let temp = Array.from({length: k}, () => 0);
    function DFS(L, s, sum){
        if (L === k && sum % m === 0) cnt++;
        if (L === k) console.log(temp, sum); // 조합 확인용 코드
        else{
            for (let i=s; i<n; i++){
                temp[L] = arr[i]  // 조합 확인용 코드
                DFS(L+1, i+1, sum+arr[i]);
            }
        }
    }
    DFS(0, 0, 0);
    return cnt;
}

[ 2, 4, 5 ] 11
[ 2, 4, 8 ] 14
[ 2, 4, 12 ] 18
[ 2, 5, 8 ] 15
[ 2, 5, 12 ] 19
[ 2, 8, 12 ] 22
[ 4, 5, 8 ] 17
[ 4, 5, 12 ] 21
[ 4, 8, 12 ] 24
[ 5, 8, 12 ] 25
2