[알고리즘] 백준 15655 - N과 M

https://www.acmicpc.net/problem/15655

문제설명
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

풀이방법

• permutation함수는 n과 m, arr를 인수로 전달받는다.
• result 배열에는 길이가 m인 수열이 저장된다.
• 그리고 isSelected는 길이가 n이고, false로 초기화되어 있다.
  각 수열에는 중복된 값이 들어가면 안되기때문에 isSelected배열을 방문체크배열로 사용할 것이다.
• 수열은 오름차순이여야 하기때문에 우선 arr배열을 오름차순으로 정렬해 준다.

---

• findPermutation함수
  - 매개변수로 arr의 index를 의미하는 cur와, 재귀함수를 호출하며 생성할 수열의 정보를 담을 numArr를 전달한다.
  - cur이 m과 같아지면 result배열에 현재까지 생성한 수열을 넣어준다.
  여기서 주의할점! result.push(numArr) 이렇게 해주면 numArr의 주소값이 result에 들어가서 findPermutation이 종료되고 난 후엔 result에 들어간 모든 수열이 같은 값을 출력한다!!!!!
  그래서 ★spread연산자를 사용해 numArr의 값과 똑같은 값을 가지는 새로운 배열을 만들어 result에 넣어준다.★
  - for문을 보면 만약 해당 호출의 numArr를 구성할때 isSelected내의 값들을 검사해서 이미 사용된 값이면 continue를 사용해 다음index를 검사한다.
  그리고 numArr[cur] = arr[i];이 부분이 수열에 값을 넣는부분인데, 배열의 cur번째값으로 arr의 i번째 값을 넣는다. 이부분을 잘 이해해야한다!!!! 재귀함수가 호출되는 순서를 적어봤는데, for문내의 i와 잘 연결해서 추론해보면 이해가 될것이다..!
  

function permutation(n, m, arr) {
  const result = [];
  const isSelected = Array.from(n).fill(false);

  arr.sort((a, b) => a - b);
  function findPermutation(cur, numArr) {
    if (cur === m) {
      result.push([...numArr]);
      return;
    }

    for (let i = 0; i < n; i++) {
      if (isSelected[i]) {
        continue;
      }
      isSelected[i] = true;
      numArr[cur] = arr[i];
      findPermutation(cur + 1, numArr);
      isSelected[i] = false;
    }
  }

  findPermutation(0, []);
  console.log(result);
}

permutation(4, 2, [4, 5, 2, 9]);