[ 자바스크립트(JavaScript) ] section08 - 10 - 순열구하기

📍 section08 - 10 - 순열구하기

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

// 입력
3 2
3 6 9
 
// 출력
3 6
3 9
6 3
6 9
9 3
9 6

 

이전에 풀었던 중복을 허락하여 순열 구하기와 비슷한 문제이지만 이번엔 중복을 허락하지 않는 조건에서 푸는 문제다. 중복을 허락하지 않았을 때 나올 수 있는 전체 경우의 수는 3*2=6이다. 핵심 포인트는 visited 배열을 선언하여 이전에 방문했던 index는 제외하고 방문하면 중복되지 않은 값이 나온다. 또한, 방문하고 다시 올라갈 때 visited를 0으로 바꿔줘야 다음 L에서 index를 순서대로 방문한다는 점이다. visited를 0으로 바꿔주지 않으면 출력이 [3, 6], [3, 9]으로만 나온다. 마지막에 출력할 때는 answer에 얕은복사slice로 push했다.

 

 

 

let n = 3;
let m = 2;
let arr = [3, 6, 9];
 
console.log(solution(n, m, arr));
 
function solution(n, m, arr){
  let temp = Array.from({length: m}, ()=>0);
  let visited = Array.from({length: n}, ()=>0);
  let answer = [];
 
  function DFS(L){
    if (L === m){
      answer.push(temp.slice());
    }else{
      for (let i=0; i<n; i++){
        if (!visited[i]){
          visited[i] = 1  // 방문처리
          temp[L] = arr[i];
          DFS(L+1);
          visited[i] = 0  // 방문 후 다시 올라갈 때 원상복구
        }
      }
    }
  } 
 
  DFS(0)
  return answer;
}