[JS] 코딩 테스트 문제 : 중복순열 구하기 [재귀함수]

문제 : 중복순열 구하기

문제 설명

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

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제 1

3 2

▣ 출력예제 1

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
9

내코드

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

  // arr : 현재 까지의 구슬 집합을 의미할 배열 파라미터, count : 총 구슬 나열 횟수
  // 위 파라미터를 가지고 구슬 집합을 채워가는 재귀함수 DFS 선언
  function DFS(arr = [], count = 0) {
    // m 번까지 뽑은 상황에서 현재 arr 배열을 정답배열에 추가
    if (count === m) {
      answer.push(arr);
    } else {
      // 현재 arr 배열에 i 값을 추가한 배열을 인자로 DFS 함수를 재귀적으로 호출
      for (let i = 1; i <= n; i++) {
        DFS([...arr, i], count + 1);
      }
    }
  }
  DFS();
  return answer;
}

풀이

1. 현재 까지의 구슬 집합을 의미할 배열 인자 arr 과 총 구슬 나열 횟수를 의미할 인자 count 를 가지는 재귀함수 DFS 선언
2. i 는 1 부터 n 까지 1씩 증가하는 반복문 안에서 현재 arr 배열에 i 값을 추가한 배열을 인자로 DFS 함수를 재귀적으로 호출
3. 만약 m 번까지 모두 뽑은 상황에서 현재 arr 배열을 정답 배열에 추가
4. 재귀 함수가 모두 종료되고 정답배열 반환

보완할 수 있는 부분

// 기존코드  
function DFS(arr = [], count = 0) {
  if (count === m) {
    answer.push(arr);
  } else {
    for (let i = 1; i <= n; i++) {
      DFS([...arr, i], count + 1);
    }
  }
}

// 보완코드  
// count 변수 필요없이 배열의 길이로 사용해도 동일하게 작동
function DFS(arr = []) {
  if (arr.length === m) {
    answer.push(arr);
  } else {
    for (let i = 1; i <= n; i++) {
      DFS([...arr, i]);
    }
  }
} 

count 인자 필요없이 배열의 길이로 사용해도 동일하게 작동

다른 해결 방법

// 정답지 방법
function solution(n, m) {
  let answer = [];
  // 현재 구슬 집합을 의미할 길이가 m 이고 0 으로 채워진 배열 tmp 생성
  let tmp = Array.from({ length: m }, () => 0);

  // 뽑을 공의 순서를 의미할 L 파라미터를 가지고 구슬 집합을 채워가는 재귀함수 DFS 선언
  function DFS(L) {
    // m 번까지 뽑은 상황에서 현재 tmp 배열을 정답배열에 추가
    if (L === m) {
      answer.push(tmp.slice());
    } else {
      // tmp 배열 에 L 번째 값을 반복문안에서 i 값으로 변경 후 L + 1 값을 인자로 DFS 함수를 재귀적으로 호출
      for (let i = 1; i <= n; i++) {
        tmp[L] = i;
        DFS(L + 1);
      }
    }
  }

  DFS(0);
  return answer;
}

풀이

1. 현재 구슬 집합을 의미할 길이가 m 이고 0 으로 채워진 배열 tmp 생성
2. 뽑을 공의 순서를 의미할 인자 L 을 가지고 구슬 집합을 채워가는 재귀함수 DFS 선언
3. tmp 배열에 L 번째 값을 반복문 안에서 i 값으로 변경 후 L + 1 값을 매개변수로 DFS 함수를 재귀적으로 호출
4. m 번까지 모두 뽑은 상황에서 현재 tmp 배열을 정답배열에 추가
5. 재귀 함수가 모두 종료되고 정답배열 반환

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64102&tab=curriculum