[JavaScript/section 8] 10 - 순열 구하기

📌 10 - 순열 구하기

10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하는 문제이다.

중복순열 구하기 문제와 다른 점은 중복없이 순서에 상관있게 선택한다는 점이다.  만약 3개의 자연수가 주어지고 이 중 2개를 뽑아 일렬로 나열하는 방법은 다음 그림과 같이 총 6가지이다.

 

👍 풀이 방법

ch 배열은 tmp 배열에 어떤 수가 선택되었는지 확인하기 위한 배열이다. (중복 검증)

• ch[i]의 값이 0이면 선택되지 않았다는 것이므로 선택해도 된다는 의미이다. 반대로 ch[i]의 값이 1이면 이미 선택되었다는 것이므로 건너뛴다.
• L(트리의 레벨)이 m과 같다면 하나의 경우가 완성된 것이므로 tmp 배열을 얕은 복사하여 answer 배열에 추가한다.
• DFS 함수의 호출이 끝난 다음엔 ch[i](이전에 선택한 숫자)를 0으로 재할당 해야한다.

그림으로 그려보는 것이 이해하는데 도움이 될 것이라고 생각한다.

function solution(m, arr) {
  const answer = [];
  const n = arr.length;
  const ch = Array.from({ length: n }, () => 0);
  const tmp = Array.from({ length: m }, () => 0);

  function DFS(L) {
    if (L === m) {
      answer.push(tmp.slice());
    } else {
      for (let i = 0; i < n; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          tmp[L] = arr[i];
          DFS(L + 1);
          ch[i] = 0;
        }
      }
    }
  }
  DFS(0);

  for (let [a, b] of answer) {
    console.log(a, b);
  }

  return answer.length;
}

let arr = [3, 6, 9];
console.log(solution(2, arr));

 

📝 한 마디 남기며..

이해하는데 어려울 수 있는 문제라고 생각합니다. 코드를 따라가며 그림으로 그려보는 것이 이해하는데 도움이 될 수 있지만 그래도 어렵다는 생각이 든다면 댓글로 남겨주세요~ 좋은 하루 되시기 바랍니다😊