[JavaScript/section 8] 08 - 중복순열 구하기

📌 08 - 중복순열 구하기

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

입력예제
3 2
출력예제
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

재귀를 알지 못했다면 이중 for 문(뽑는 횟수 2번)을 이용해 풀었을 것이다. 게다가 다중 for 문과 재귀는 같다고 해도 무방하다. 하지만 왜 더 간단한 이중 for 문을 사용하지 않고 재귀를 이용해 문제를 풀어야 할까 하는 의문이 생긴다..🤔 

 

for 문을 이용한 방법

function solution(n) {
  let answer = [];

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      answer.push([i, j]);
    }
  }

  return answer;
}

console.log(solution(3));

이중 for 문을 이용해 풀어보았다❗ 실행해보면 재귀를 이용한 방법과 같은 결과를 보여준다는 것을 알 수 있다.

 

하지만 뽑는 횟수가 3번이라면❓

function solution(n) {
  let answer = [];

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      for (let k = 1; k <= n; k++) {
        answer.push([i, j, k]);
      }
    }
  }

  return answer;
}

console.log(solution(3));

😵 뽑는 횟수가 늘어날수록 for 문도 같이 늘어나 코드 수정이 필요하다. 자주 수정이 필요한 코드는 좋지 못한 코드이다. 반면에 재귀를 이용하면 이러한 불편함을 해결할 수 있다.

 

👍 재귀를 이용한 풀이 방법

재귀를 돌면서 L(트리 레벨)이 m(뽑는 횟수)과 같다면 하나의 경우의 수가 완성된 것이므로 tmp를 얕은 복사(slice) 하여 answer 배열에 추가한다. tmp를 answer 배열에 바로 추가하면 배열의 모든 값들이 같은 메모리 주소를 가지게 되므로 마지막 값인 [3, 3] 값만 존재하게 된다.

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