01_orderOfPresentation
문제
말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.
선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.
김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.
총 조의 수 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수도코드
N에 맞는 배열을 만드는 것은 팩토리얼이다.
발표순서 최대 크기는 12!이다.
이 순열을 전부 생성해서 K에 맞는 값을 찾는 것은 수행 속도에 문제가 있다.
따라서 K 배열에 맞게 for문으로 순차 진행하면서 나오는 값들의 이전 경우의 수를 계산해서 더하는 방식을 취해본다.Code
function orderOfPresentation (N, K) {
// TODO: 여기에 코드를 작성합니다.
// N=3/ K=[2,1,3]을 예시로 들어보자
// 우선 수열을 만들어준다.
const factorial = (n) => {
if(n <= 1) return 1;
return n * factorial(n - 1);
}
// 발표 순서를 담는 변수 order생성
let order = 0;
// 어떠한 조가 이미 포함되었는지 확인하는 배열 생성
// 인덱스는 0부터 시작하지만 조는 1부터 시작하기 때문에 +1을 해준다(더미데이터)
// N=3/ isUsed = [false(dummy), false, false, false]
const isUsed = Arrary(N+1).fill(false);
// K 길이만큼 순회한다
// K=[2,1,3] 이므로 2 -> 1 -> 3 순으로 순회 예정
for(let i=0; i < K.length; i++) {
// K의 i번째 수를 num으로 지정
// num = 2
const num = K[i];
// 사용체크 배열에 true값으로 변경
// isUsed = [false, false, true, false]
isUsed[num] = true;
// num보다 앞에 올 수 있는 숫자를 복제
// copyedArr = [false]
const copyedArr = isUsed.slice(1, num);
// 사용하지 않은 수의 개수를 구한다.
// validNum = 1
const validNum = copyedArr.filter((el) => el === false).length;
// 사용하지 않은 수 그 전까지의 모든 경우의 수를 구해준다.
// i는 0부터 시작하므로 N에서 남아있는 수를 구할 때 -1을 해준다.
// formerNum = 1*factorial(3-0-1) -> 2
const formerNum = validNum * factorial(N-i-1);
// order = 2
order = order + formerNum;
}
// 첫번째 order는 2가 나왔다. 다음 경우도 간략하게 정리해보자.
// i = 1 / num =1
// isUsed = [false, ture, true, false]
// copyedArr = []
// validNum = 0
// fomerNum = 0
// order = order(2) + 0 -> 2
// i = 2 / num = 3
// isUsed = [false, true, true, true]
// copyedArr = []
// validNum = 0
// fomerNum = 0
// order = order(2) + 0 -> 2
// 결과적으로 3을 이용해서 만든 배열 중 [2,1,3]은 2(3번째)에 위치한다.
return order;
}