[JS] orderOfPresentation

조의 발표순서를 듣고 모든 조의 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 들은 조의 발표순서가 몇 번째 경우의 수인지 대답해야한다.

입력

인자1 (N): 총 조의 수 (1 이상 12이하) Number타입
인자2 (K): 중복되는 조가 없는 조의 발표순서를 담은 배열 Number타입의 Array

출력

조의 발표순서가 경우의 수의 몇번째인지 나타내는 수 Number타입

예시

let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output); // 3

작성

발표 순서를 만드는 것은 순열이므로, 발표 순서의 최대 크기는 !12이다.
순열을 전부 생성하면 일반적인수행속도를 상회하므로 다른방법으로 접근해야한다.

조의 수, 발표순서를 담은 배열 을 인자로 받는 함수

function orderOfPresentation(N, K){
}

수를 입력받아 그 수의 펙토리얼을 리턴하는 함수

function factorial (n) { 
  if(n <= 1) return 1;
  return n * factorial(n - 1);
};

발표 순서를 담는 즉 결과값이 되는 변수를 만든다.
let order = 0;

어떤 조가 사용 되었는지 담는 배열을 생성한다.(0번째 인덱스는 더미 데이터)
const isUsed = Array(N + 1).fill(false);

발표순서를 담은 배열을 순회하는 반복문 작성
for(let i = 0; i < K.length; i++){}

발표순서의 i번째 조를 변수에 할당한다.
const num = K[i];

조가 사용 되었는지 담는 배열에 true로 체크한다.
isUsed[num] = true;

앞에 오는 조들의 배열을 변수에 할당한다.
const candidates = isUsed.slice(1, num);

아직 사용되지 않은 조들의 길이를 구한다.
const validCnt = candidates.filter(el => el === false).length;

아직 사용되지 않은 조들의 전의 모든 경우의 수를 카운트한다.
const formerCnt = validCnt * factorial(N - i - 1);

결과값변수에 추가한다
order = order + formerCnt;

반복문이 끝나면 결과값을 리턴한다.

코드

function orderOfPresentation(N, K){
  function factorial (n) {
  	if(n <= 1) return 1;
    return n * factorial(n - 1);
  };
  let order = 0;
  const isUsed = Array(N + 1).fill(false);
  for(let i = 0; i < K.length; i++){
    const num = K[i];
    isUsed[num] = true;
    const candidates = isUsed.slice(1, num);
    const validCnt = candidates.filter(el => el === false).length;
    const formerCnt = validCnt * factorial(N - i - 1);
    order = order + formerCnt;
  }
  return order;
}