순열로 모든 경우의수 배열로 정리하기

오늘은 코플릿 toy문제를 풀다가 막혔던 부분이 풀린 기념으로 포스팅을 작성해보려고 한다. 

이 문제를 풀면서, slice를 제대로 쓰는법과 스프레드 문법에 조금 더 익숙해 진것 같아 뿌듯하다.(하지만 코플릿 문제가 시행시간초과로 안풀렸다는건 안비밀ㅋㅋㅋ)

내가 막혔던 부분은 숫자 n을 입력 받았을때, 순열로 n의 모든경우의 수를 배열로 정리하고 싶었다. 

 

즉, 3을 입력 받았을때 => [1, 2, 3], [1, 3, 2], ..., [3, 2, 1]와 같이 말이다. 

 

여기서 재귀함수를 사용하게 되는데, 이는 계속 반복되는 작업이기 때문이다. 

예를 들어, 

 

<[1, 2, 3, 4]의 경우의 수를 모두 구하려고 한다면>

  4를 고정, 나머지 3개의 모든 경우의수

  3를 고정, 나머지 3개의 모든 경우의수

  2를 고정, 나머지 3개의 모든 경우의수

  1를 고정, 나머지 3개의 모든 경우의수

라는 과정을 거치게 되면 되고, 

 

<[1, 2, 3]의 모든 경우의 수를 구하려고 한다면>

  3를 고정, 나머지 2개의 모든 경우의수

  2를 고정, 나머지 2개의 모든 경우의수

  1를 고정, 나머지 2개의 모든 경우의수

 

<[1, 2]의 모든 경우의 수를 구하려고 한다면>

  2를 고정, 나머지 1개의 모든 경우의수

  1를 고정, 나머지 1개의 모든 경우의수

 

<[1]의 모든 경우의 수를 구하려고 한다면>

  해당 숫자 하나만 있는 배열, [1]이 모든 경우의 수가 되게 된다. 

 

즉, 해당 배열의 요소를 각각 하나씩 고정시킨다음, 나머지 요소들로 구한 경우의수를 고정시킨것과 합하게 되면 모든 경우의 수를 구하게 된다. 

 

이는 아래와 같은 코드로 나타나게 된다. 

 

 

const getPermutations= function (arr) {

const results = [];   

if (arr.length === 1) return arr.map((value) => [value]);      // arr안의 요소가 1개일때, 해당요소 자체를 value로 return

 

 

 

arr.forEach((value, idx, self) => {

 

const fixed = value;   // 배열의 요소 하나하나를 순차적으로 고정. 

const rest = [...arr.slice(0, idx), ...arr.slice(idx+1)];    // rest 는 fixed이외의 숫자만 남은 배열 

const permutations = getPermutations(rest);            // fixed의 이외의 숫자로 구한 순열이, 한가지 숫자를 고정하고 얻을 수 있는 순열.  

const attached = permutations.map(permutation => [fixed, ...permutation]);  // 실제로 고정된 것과 나머지로 구한 순열을 한 배열로 합치.

 

results.push(...attached);  // 해당 배열을 result에 넣고, 그 다음 fixed로 이동하여 해당 과정 반복. 

})

return results;

};