[Algorithm] 중복순열 구하기(DFS)

❐ 중복순열 구하기

▶︎ 문제

   1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 

 

▷ 입력 예제

3 2

 

▶︎ 출력 예제

1 1
1 2 
1 3
2 1
2 2
2 3
3 1
3 2
3 3

 

▷ 문제설명

일반적으로 순열은 서로 다른 n개 중 r개를 순서를 고려하여 나열하는 것을 말한다. 한 번 고른 것은 다시 고를 수 없는 것이 원칙이나, 중복순열의 경우에는 특별히 중복을 허용한다. 

 

문제는 3까지의 번호가 적힌 구슬에서 두 개를 뽑아 중복을 허락하여 나열하는 경우의 수를 구하라고 한다. 

즉, 주머니에 1부터 3까지 적혀있는 구슬 세개가 들어있다고 가정했을 때 ① 주머니에 들어있는 세개의 구슬 중 하나를 뽑아서 첫번째 자리 수를 정하고 ② 뽑은 구슬을 다시 주머니에 넣은 다음, ③ 주머니에 있는 3개의 구슬 중 하나를 뽑아서 두 번째 자리 수를 정하는 경우의 수를 구하는 것과 같다.

 

이를 for문을 이용한 코드로 나타내면 다음과 같다. 

function solution(n, m) {
    // 이중 for문
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= m; j++) {
            console.log(i, j);
        }
    }
}

solution(3, 2);

 

하지만 for문 만을 이용해 중복순열을 구현할 경우에는 문제가 있다. 인자의 값이 변할 경우 코드도 매번 변해야 하는 것이 문제다.

예를 들어 solution(4, 3)을 호출하여 원하는 값을 구하려면 코드는 다음과 같다. 이전에는 2였던 m의 값이 3으로 변하면서 이중 for문 이었던 코드가 삼중 for문으로 변했다. 

function solution(n, m) {
    // 삼중 for문
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            for (let k = 1; k <= n; k++) {
                console.log(i, j, k);
            }
        }
    }
}

solution(4, 3);

 

이것은 좋은 코드라고 볼 수 없다. 인자 m의 값이 변할 때마다 for문을 몇번 중첩할 지 계속 변경해주어야만 원하는 값을 출력할 수 있기 때문이다. 

따라서 for문과 재귀함수를 사용해서 중복순열을 구하는 방법이 더 합리적이다. 

 

 

▶︎ 내 답안

function solution(n, m) {
    let answer = [];
    let tmp = Array.from({ length: m }, () => 0);
    function DFS(L) {
        if (L === m) {
            answer.push(tmp.slice());
        } else {
            for (let i = 1; i <= n; i++) {
                tmp[L] = i;
                DFS(L + 1);
            }
        }
    }

    DFS(0);
    return answer;
}

console.log(solution(3, 2));

 

if (L === m) {
    answer.push(tmp.slice());
}

slice 메서드는 어떤 배열을 얕게 복사한 복사본을 새로운 배열 객체로 반환하는 역할을 한다.

slice 메서드를 적용한 값을 push 하는 이유는 tmp 배열의 값을 변경하고 그대로 push 할 경우 배열의 주솟값이 저장되므로 answer 배열 안에 들어가는 배열들은 모두 같은 값을 가지고 있기 때문이다. 따라서 얕은 복사를 통해 새로운 배열 객체를 만들어 push 해야 원하는 값을 구할 수 있다.