[코딩테스트] 중복순열 구하기 (feat. javascript)

1. 문제

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

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

 

 

1) 순열과 중복순열

순열은 주어진 원소 집합에서 일부 원소를 '순서대로' 배열하는 방법을 말한다. 

따라서 중복 순열은 중복을 허용하면서, 원소를 순서대로 배열하는 방법을 의미한다.

 

순열 개수 구하는 공식 : n​Pr​=P(n,r)=(n−r)!n!

중복 순열 개수 구하는 공식 : n∏r = n^r

 

ex) 1부터 3까지의 번호를 2번 뽑아 나열

3^2 = 9

 

 

2. 풀이

해당 문제는 1부터 N까지의 번호가 적힌 구슬을 M번 뽑아서 순차적으로 나열하는 문제이다.

 

 

따라서 위처럼 트리의 가지가 N개 뻗어진다.

트리 순서대로 [1, 1], [1, 2], [1, 3], [2, 1] ... 이렇게 출력되도록 코드를 짜면 된다.

 

1) 내풀이

function solution(n, m) {
    let answer = [];
    let tmp = Array.from({ length: m }, () => (0));

    function DFS(L) {
        if (L === m) {
            //종료조건
            return console.log(tmp)
        } else {
            for (let i = 1; i <= n; i++) {
                tmp[L] = i;
                DFS(L + 1)
            }
        }
    }

    DFS(0);
    return answer = Math.pow(n, m);
}

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

//
11
12
13
21 
22 
23 
31 
32 
33 
9

 

값이 배열로 출력되어야 하기 때문에 길이가 2인 tmp 배열을 만들어줬다. 

그리고 구슬은 M번 뽑기 때문에 종료조건을 L(길이, 뽑은 개수)이 M과 같을 때로 설정해준다.

 

else에서 for문을 통해 가지를 3개 만들어주고, 그 안에서 tmp[L] 안에 i의 값을 넣어준다.

tmp[0] = 1 이런식으로 값이 들어가게 된다.  

 

그 후 DFS(L+1)을 호출하면, 즉시 DFS(0+1) 함수가 호출되고, 기존의 DFS(0)은 스택에 저장된다.

 

0+1은 M보다 작으므로 else로 와서 다시 for문을 반복한다.

이때 tmp[1] = 1 이런식으로 값이 들어가게 된다.

 

DFS(L+1)이 호출되면 이전과 마찬가지로 DFS(1)은 멈추고 DFS(2)가 호출된다.

해당 값은 M과 같으므로 종료조건에 포함되어 console.log(tmp)를 출력한다.

 

콘솔창에 [1, 1]이 출력되고, 다시 DFS(1) for문으로 돌아와서 tmp[1] = 2를 실행한다.

위 과정을 반복하여 모두 출력해준 후, 마지막에 해당 중복순열의 개수를 출력해준다.

 

중복순열의 개수는 n^M이므로 pow를 통해 출력해준다. 

 

 

2) 강의풀이

function solution(n, m) {
   ...
    function DFS(L) {
        if (L === m) {
            //종료조건
            answer.push(tmp.slice());
        } else {...}
    }

    DFS(0);
    return answer;
}

 

강의에서는 answer에 값을 모두 push 한 뒤, 해당 배열을 출력했다.

이러면 콘솔창에서 해당 배열의 길이도 같이 나오기 때문이다. 

 

tmp 뒤에 slice()를 붙이지 않으면, 값이 모두 마지막 tmp의 값으로 변하기 때문에 반드시 붙여줘야 한다. 

 

 

 

 

*다중for문을 쓰지 않고 재귀를 사용하는 이유*

 

for문을 사용하면 재사용하기 쉽지 않기 때문에 재귀를 사용하는 것이 좋다.

만일, 위 문제를 for문으로 풀었다고 하면 for를 두 개 돌려서 풀었을 것이다. 

 

하지만 만일 M값이 3, 4 ... 처럼 바뀌게되면 그때마다 코드를 수정해야 한다.

 

 

 

 --------

수학 공부좀 열심히 할걸... 순열이 뭐지? 이러고 있네ㅠ