1번문제

말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.

선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.

김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.

총 조의 수 N과 선생님이 말씀하시는 발표 순서 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.

모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다.
ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

예시

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

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

먼저 생각
모든 가능성의 배열을 만들어 놓고...... 그 배열을 맞는지 아닌지 찾아볼까??
라고 생각했는데...

입력되는 숫자가 12까지 라곤 했지만.....너무 많은 배열이 만들어지고 해서
너무 오래걸리니 반대로

입력된 배열의 규칙성을 찾아서 거꾸로 순서를 찾아가보자 !!~~

🍩꼭 알고 가야할것 ..
1.재귀함수 =>
입력된 수의 모든 경우의수를 구한다. 왜냐하면...두번째로 나온다.

2.배열의 규칙성 파악
[2,3,1] 입력되면

0번째 인덱스는 2다 그렇다면
1로 시작하는거는 전부 나왔다는 뜻~~ 이해감?
0번째 [1,2,3]
1번째 [1,3,1]
2번째 [2,1,3]
3번째 [2,3,1] <- 이거다
4번째 [3,1,2]
5번째 [3,2,1]

3번째 랑 [2,3,1]를 연결 시켜보자

Array.prototype.fill() 사용법
fill(value)
fill(value, start)
fill(value, start, end)

fill(value)
fill(value, start)
fill(value, start, end)

정답코드

function orderOfPresentation(N, K) {
  
  // factorial 함수 생성
  const factorial = n => {
    if (n<=1) return n;
    return n * factorial(n-1);
  }
  
  // 발표순서 담을 변수는 order
  let order = 0;
  
  // 어떠한 조가 이미 포함되었는지 확인하기 위해 isUsed 배열을 생성
  // Array(N)이 아니라 (N+1)임에 유의하라
  const isUsed = Array(N + 1).fill(false);
  
  // K의 개수만큼 반복
  for (let i = 0; i < K.length; i++) {
    
    // K의 i번째 조를 num에 담는다.
    const num = K[i];
    
    // 사용했는지 판별하기 위하여 isUsed에 true로 값을 바꿈 
    isUsed[num] = true;
    
    // 아래는 i번째 원소를 기준으로 i번째 숫자의 맨 처음 경우의 수를 구해서 더해주는 과정이다.
    
  	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;
    
}