[코딩테스트] 재귀로 순열 구하기

1. 문제 : 순열 구하기

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

 

순열은 주어진 집합에서 일부 원소를 순서대로 나열하는 것을 말한다.

중복 순열과 달리, 집합에서 각 원소들이 겹치면 안 된다. 

 

2. 풀이

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

    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 //back하는 지점
                }
            }
        }
    }

    DFS(0);
    return answer;
}

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

 

순열 구하는 방법은 중복 순열 구하는 방법과 크게 다르지 않다.

값을 넣을 때, 해당 값이 이미 들어간 값인지 체크한 후, 들어가지 않은 값만 넣어주면 된다.

 

체크 배열을 만들어, 해당 인덱스에 있는 값이 tmp에 들어가 있는지 체크할 것이다. 

 

 

 

트리는 위처럼 생성된다.

0, 1이 집합의 길이이고, 0, 1, 2가 각각의 원소이다.

 

여기서 아래로 내려갈 때, 각 원소가 tmp 안에 들어가고 이때 체크 배열 안에 해당 값이 들어갔다는 것을 체크해줘야 한다.

그리고 위로 올라올 때, 원소가 tmp에서 빠지게 되므로 체크 배열 값을 바꿔주면 된다. 

 

값이 있다면 1, 없다면 0으로 체크 배열에 넣어줄 것이다. 

 

 

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

 

우선, arr.length를 n 변수에 저장해준다.

그 후 체크 배열(ch)을 만들어, arr의 길이만큼 0으로 초기화해준다.

그럼 ch은 [0, 0, 0] 이렇게 될 것이다. 

 

그리고 집합을 넣어줄 tmp도 빈배열로 선언해 준다.

 

 

function DFS(l) {
  if (l === m) {
    answer.push(tmp.slice());
  } else {
    ...          
  }
}

 

종료 조건은 길이가 m과 같을 때까지로 설정해 준다.

여기서 말하는 길이는 뽑은 개수(집합의 길이)라고 생각하면 된다.

 

m개만큼 숫자를 뽑았다면, answer에 해당 값을 넣어준다.

이때 slice를 사용하지 않으면 맨 마지막 값만 들어가기 때문에 반드시 써줘야 한다.

 

 

 

*slice 사용 이유

 

자바스크립트에서 배열은 객체로 취급된다.

따라서 다른 배열이나 변수에 할당할 때, 값이 복사되는 것이 아니라 참조가 복사된다.

즉, 해당 값을 가리키는 주소값이 복사되는 것이다. 

 

answer.push(tmp)를 하게 되면 현재 tmp의 주소값이 복사된다.

따라서 tmp의 값이 바뀔 때마다 answer에 들어간 값도 바뀌게 된다.

 

값이 바뀌는 게 싫다면, tmp을 복사한 새로운 배열을 answer에 넣어줘야 한다.

그래야 answer에 들어간 tmp의 주소가 각각 달라지고, tmp의 값이 바뀌어도 answer 안에 있는 값들은 변하지 않는다.

 

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 //back하는 지점
    }
}

 

 

그 후 for문을 통해 가지를 만들고, 원소의 개수만큼 반복해 준다.

 

만일 해당 값이 들어있지 않다면, 체크 배열의 값을 1로 바꿔주고 tmp에 값을 넣어준다.

그리고 DFS(l+1)을 호출해 준다.

 

재귀함수를 호출한 뒤에 있는 코드들은, 가지가 올라올 때 실행된다.

따라서 체크 배열의 값을 다시 0으로 바꿔준다.

 

 

--------

처음에 내가 풀었을 땐, for문 안에서 IndexOf를 사용했었다.

tmp에 해당 값이 없는 경우에만 넣게 하려고 한 것인데, 재귀함수 안에서 Indexof를 사용하면 성능이 느려진다..

따라서 위와 같은 방법을 사용하는 게 좋다.