줄 서는 방법

문제설명

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 > 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

입출력 예

n	k	result
3	5	[3, 1, 2]

입출력 예시 설명

입출력 예 #1
문제의 예시와 같습니다.

문제 풀이

1. n만큼 숫자 배열을 만든다.
2. factorial값(n으로 만들 수 있는 경우의 수)을 구한다.
3. 배열은 0부터 시작하니까 k를 1줄여준다.
4. answer의 길이가 n만큼까지 while문을 돌린다.
5. fac = fac/arr.length => n-1까지의 경우의 수
6. k를 fac으로 나눈 값이 선택한 숫자가 된다.(n이 3, k=5인 경우 2x1으로 k를 나누면 선택해야할 숫자를 알 수 있다.)
7. answer에 선택한 숫자를 넣어준다.
8. k는 fac로 나눈 나머지로 바꿔준다.
9. arr에서도 선택한 숫자를 제거.

function solution(n, k) {
  var answer = [];
  let arr = [];
  for (let i = 1; i <= n; i++) arr.push(i);
  let fac = arr.reduce((acc, val) => acc * val, 1);
  k--;
  while (answer.length !== n) {
    fac = fac / arr.length;
    // console.log(fac);
    let temp = arr[Math.floor(k / fac)];
    answer.push(temp);
    k = k % fac;
    arr = arr.filter(e => e !== temp);
  }
  return answer;
}