[ 백준 / javascript ] 15649 N과 M(1)

 

문제 설명)

 

자연수 N과 M이 주어졌을 때, 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력하는 문제

 

조건) 중복되는 수열은 여러 번 출력하면 안 됨 / 수열은 사전 순으로 증가하는 순서로 출력 

 

 

풀이)

const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map((a) => Number(a));

function nm(arr, j, res) {
  if (j === input[1]) {
    console.log(res.join(" "));
    return;
  }
  let i = 1;
  while (i <= input[0]) {
    if (arr[i] !== 0) {
      let temp = JSON.parse(JSON.stringify(arr));
      temp[i]--;
      let temp2 = JSON.parse(JSON.stringify(res));
      temp2.push(i);
      nm(temp, i, j + 1, temp2);
    }
    i++;
  }
}

const arr = Array.from({ length: input[0] + 1 }, () => 1);
nm(arr, 0, []);

 

먼저, N+1 크기의 배열 arr을 생성하고, 모든 요소를 1로 초기화했다. 이 배열은 이미 선택한 숫자의 인덱스를 가리키는 요소를 0으로 바꿔서 이미 선택한 숫자를 추적해준다!

nm 함수 내에서는 1부터 N까지의 숫자를 반복하여 arr [i] 값이 0이 아닌지 확인해 줬다. 아닌 경우 아직 선택 가능한 숫자이므로 결과 배열 res에 추가하고, nm함수를 다시 호출하는 식으로 재귀적으로 진행해 주었다. j 변수는 현재까지 선택한 숫자의 수를 나타내서 이 수가 M과 같아지면 하나의 수열이 구성된 것이기 때문에 해당 수열을 출력해 주고 함수를 return 하였다. 이렇게 해주면 모든 경우의 수열이 출력된다!

 

+

 let temp = JSON.parse(JSON.stringify(arr));

 

이 부분은 깊은 복사를 하는 부분이다. 나는 처음에 이런 식으로 안 하고 값을 넘겨줘서 재귀적으로 호출이 되다가 수열이 완성돼서 return 되어 돌아왔을 때 res배열이 함수가 호출이 되기 전 상태여야 하는데 완성된 그대로라 값이 계속 누적된 채로 추가되어 출력됐었다..ㅎ