📌 발표순서 구하기
팩토리얼을 이용하여 발표순서를 구하는 것이다.
김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.
총 조의 수 N과 선생님이 말씀하시는 발표 순서 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.
모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정
ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
인자 1: N
Number 타입의 1 <= N <= 12인 조의 개수
인자 2: K
Number타입의 Array (0 <= index)
ex) n이 3이고 k가 [2, 3, 1]일 경우
모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,
반환하는 값은 3이 됩니다.주의사항
k내에 중복되는 요소는 없다고 가정합니다.
입출력 예시
- let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output); // 3- output = orderOfPresentation(5, [1, 3, 2, 4, 5])
console.log(output); // 6
문제에서 먼저 발표 순서에 대한 경우의 수를 차례대로 구한 뒤라는 말이 있다. 이건 곧 팩토리얼을 이용하게 되는 것이다. 우선 첫째로 팩토리얼 보조함수를 생성한다. 이 함수는 이후에 이용한다
const factorial = (n) => {
if (n <= 1) return 1;
return n * factorial(n - 1);
};1) 발표순서를 담는 변수를 생성한다.(초기값은 0이다)
2) 총 조의 수는 N이라고 할 때, 어떠한 조가 이미 포함되었는지 확인하기 위해 배열을 생성한다.
3) 0번째는 더미데이터로 false를 생성하고, 그것들을 모두 false로 채운다.
let order = 0 const isUsed = new Array(N + 1).fill(false) // N+1을 해주는 이유는 인덱스는 0부터 시작하지만 조는 1부터 시작하기 때문이다. //K가 [2,3,1]라고 가정해보자 그리고 N이 3이다. //isUsed === [false, false, false, false] 이다.
4) K를 조회하면서 K의 i번째 조를 변수에 담는다.
5) 사용했는지 판별하기 위해 isUsed에 체크 (중복이 아니기 때문에)
6) num보다 앞에 올 수 있는 수들의 배열을 복제해서,
7) 이 중에서 아직 사용되지 않은 수의 개수를 구함.
8) 아직 사용되지 않은 수, 그 전까지의 모든 경우의 수를 카운트.
9) order에 추가.
for(let i=0; i< K.length; i++) { //K=[2,3,1] const num = K[i] //K[0] 은 2, 즉 num은 2 isUsed[num] = true //[false false true false] const candidates = isUsed.slice(1, num) // [false] const validCnt = candidates.filter((item) => item === false).length // 1개 const formerCnt = validCnt * factorial(N - i - 1); order = order + formerCnt }
발표순서를 담았던 order를 최종적으로 리턴한다.
