[ 자바스크립트(JavaScript) ] section08 - 8 - 중복순열 구하기

📍 section08 - 8 - 중복순열 구하기

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

 

// 입력
3 2

// 출력
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
9

 

입력으로 주어진 중복순열의 모든 경우의 수는 n*n 즉, 9가 된다. 그런데, 이런 중복순열 문제는 다음과 같이 for문으로 풀면 더 간단하지 않을까?

let n = 3;
let m = 2;

for (let i=1 ; i<=n; i++){
  for (let j=1; j<=n; j++){
    console.log(i, j)
  }
}

👉🏽
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

 

물론, 지금과 같은 입력에서는 답은 잘 나온다. 만약, m이 3일때(3개 중 3개를 뽑는 경우의 수)는 어떻게 구할까? 결론적으로 말하고 싶은 것은 m이 늘어날 때마다 반복문의 개수도 늘어나야하는데, 일일이 m개씩 반복문을 작성하게 되면 상당히 비효율적인 코드가 된다. 코딩 테스트처럼 입력이 여러 개인 경우 이렇게 하드코딩을 할 수도 없다. 이럴 때 재귀를 사용하여 m번 만큼 반복문을 돌면 편하게 구할 수 있다. m값이 바뀌면 m레벨만큼 재귀를 사용해 구하면 된다.

 

// 하드코딩
let n = 3;
let m = 3;

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)
    }
  }
}

👉🏽
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

 

728x90

 

재귀로 풀 때 주의할 점은 재귀로 돌고 나서 나온 arr의 값이 마지막 값만 참조하므로 얕은복사(slice)를 이용해 answer에 push해주자.

 

// 정답
let n = 3;
let m = 2;

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

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