[백준] 15649

N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

let arr;

const recurNandM = (n, m, k, isUsed, ans) => {
  if (k === m) ans.push(arr.join(" "));
  else {
    for (let i = 1; i <= n; i++) {
      if (!isUsed[i]) {
        arr[k] = i;
        isUsed[i] = true;
        recurNandM(n, m, k + 1, isUsed, ans);
        isUsed[i] = false;
      }
    }
  }
};

const nAndM = () => {
  let [n, m] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  let ans = [];
  let isUsed = Array.from({ length: 10 }, (v) => false);
  arr = Array.from({ length: m }, (v) => 0);
  recurNandM(n, m, 0, isUsed, ans);
  console.log(ans.join("\n"));
};

nAndM();

반성회

처음엔 arr도 인자로 받았는데 (전역변수를 쓰지 않겠다는 의지...) 그렇게 하니까 무한루프를 돌아서 arr만 전역변수로 빼 버렸다

• isUsed : 중복 없이 M개를 골라야 하므로, 이미 사용한 숫자는 true로 체크하는 배열
• arr : M자리의 수열을 저장하는 배열, 재귀를 들어갈 때마다 특정 자리수 (k) 에 숫자를 채워넣는다
• k : 수열의 몇 번째 자리를 계산하는지 나타내는 자리수
• ans : 나중에 수열을 한꺼번에 출력하기 위해 만든 수열을 저장하는 배열

재귀 진행 순서

1. k는 자리수를 나타내고, 0번째 자리부터 채워나가므로 recurNandM의 인자 k는 0으로 설정하여 시작
2. recurNandM의 탈출조건은 k가 m일 때이다
   • k는 0부터 시작하여 m개 자리를 채우므로 k의 최대값은 m - 1이다
   • 따라서 k가 m일 땐 알고리즘 진행을 중단하고 지금까지 만든 수열을 ans에 push함
3. k가 m이 아닐 경우, k번째 자리에 값을 채워넣기 위해 반복문을 돈다
   1. 반복문의 반복자 i는 1부터 n까지 돈다(수열에 1부터 n까지의 수가 올 수 있으므로)
   2. isUsed[i] 가 true일 경우, i를 이미 사용했다는 의미이므로 반복문을 다시 돈다 (해당 자리 = k번째 자리에는 i가 올 수 없다는 뜻)
   3. isUsed[i]가 false일 경우, k번째 자리에 i를 채워넣고 재귀를 한번 더 들어가 다음 자리수에 올 숫자를 탐색한다
      1. k번째 자리에 i를 채워넣는다는 건 수열을 표현하는 배열 arr의 k번째 인덱스가 i라는 뜻이다 ⇒ arr[k] = i
      2. k번째 자리에 i를 사용했으므로, 그 뒤에 오는 자리에는 i를 사용할 수 없어 isUsed[i]를 true로 설정한다
   4. 재귀를 빠져나왔다는 건 k번째 자리에 i를 넣는 모든 경우의 수의 수열을 완성하였거나, 사용할 수 있는 숫자가 없어 재귀가 끝났다는 것을 의미하므로, k번째 자리에 i를 넣는 경우의 탐색을 중지한다
      1. 반복문을 통해 진입하는 다음 케이스에선 k번째 자리에 i를 넣지 않고 i + 1을 넣을 예정이므로, i는 사용하지 않은 상태가 되기 때문에 isUsed[i]를 false로 설정한다
   5. 반복문의 처음으로 돌아가, i + 1의 경우에 다시 과정을 진행한다
4. 모든 재귀를 빠져나와 recurNandM을 종료하고 nAndM 함수로 돌아왔다는 것은 모든 경우의 수를 탐색하여 가능한 수열을 전부 찾아냈다는 뜻이므로, ans에 저장된 모든 수열을 \n을 기준으로 구분하여 출력한다