문제
총 조의 수 N과 발표 순서 k가 주어질 때, 발표 순서가 몇 번째 경우의 수인지 구하는 함수를 짜시오.(인덱스가 아님) 단, 모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정한다.
예시
만약에 N = 3일경우, 발표순서 케이스를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]의 순서로 배열된 배열이 된다.
따라서, n이 3이고 k가 [2, 3, 1]이라면 3을 리턴해야한다.
로직
우선 이 문제는 경우의 수와 관련된 문제이다.
경우의 수 문제 중 순열(Permutaion)과 연관이 되어있다.
그런데 발표 순서를 정하는 총 경우의 수는 N!이다.
N!은 숫자가 조금만 커져도 수가 기하급수적으로 늘어난다.
N이 10만 되도 3628800이 되는 것이다!
따라서 이러한 총 경우의 수를 고려한 배열을 만들고 각각의 배열의 원소가 같은지 비교하는 방법은 경우의 수가 너무 많아지기 때문에 비효율적이다.
따라서 모든 배열의 경우의 수를 구하지 않고 몇 번째 경우의 수인지 구하는 로직을 고려해야 된다.
만약 N이 4이고, 발표 순서가 [4, 2, 3, 1]이라는 예시를 들어보겠다.
총 경우의 수는 4! = 24가지이다.
하지만 [4, 1, 2, 3]가 몇 번째인지는 계산을 통하여 쉽게 알 수 있다.
1 + 3 X 3!번째이다.
앞자리가 정해져 있는 상태에서 나머지를 줄세우는 경우의 수는 (N-1)!이기 때문이다.
그리고 그것이 세 번 반복되기 때문에 3을 곱해주는 것이다.
그리고 그 다음의 경우의 수이기 때문에 1을 더하면 된다.
이 문제의 핵심은 문제를 분리시켜서 생각해보는 것이다.
기준점은 배열의 요소이다. 위에서는 0번째 인덱스를 기준으로 생각한 것이다.
그다음에는 1번째 인덱스인 2를 기준으로 생각하는 것이다.
앞 순서가 4이고 그다음의 순서가 2인 경우 중 맨 앞의 경우(즉, [4, 2, 1, 3])가 [4, 1, 2, 3]보다 몇번째 앞서있는지를 구하면 된다.
앞의 방식대로 구하면 1 * 2!가 될 것이다.
이러한 과정을 마지막 배열의 값까지 반복시킨 다음 최종 값을 구하면 된다.
알고리즘
- 우선 factorial 값을 구하는 함수를 재귀 or 반복문을 이용하여 만든다.
- order 변수를 선언하고 0으로 초기화한다. order변수를 최종적으로 출력할 것이다.
- N개의 조 중에, 어떠한 조가 이미 포함되었는지 확인하기 위해 isUsed 배열을 생성하고 모든 값을 False로 초기화한다.
- K의 개수만큼 배열을 반복시킨다.
4-1. 우선 num 변수를 선언하고 K의 i번째 인덱스의 값으로 준다.
4-2. isUsed의 num번째 인덱스의 값을 true로 바꾼다.
4-3. isUsed 배열을 1번째 인덱스부터(0번째 아님) num번째 인덱스 전까지 복사한 다음, 배열의 길이를 구한다.
4-4. 그리고 4-3값에 (N-i-1)!을 곱한다.
4-5. 4-4에서 구한 값과 order에서 구한 값을 더한다. - order 값을 리턴한다.
코드
이러한 과정을 통하여 작성한 코드는 다음과 같다.
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;
}
console.log(orderOfPresentation(4, [4, 2, 3, 1])); // 21
