문제
말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.
선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.
김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.
총 조의 수 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풀이
- orderOfPresentation(3, [2,3,1]) 이라고 가정하면,
- 우선 arr=[1,2,3]으로 중복없이 나열하는 경우의 수는,
- arr[0]이 각각 1인 그룹, 2인 그룹, 3인 그룹으로 나눠서 생각할 수 있다
- 따라서 3 * 2!이 전체 경우의 개수다
function orderOfPresentation(N, K) {
// orderOfPresentation(3, [2,3,1]) 이라고 가정하면,
// 우선 arr=[1,2,3]으로 중복없이 나열하는 경우의 수는,
// arr[0]이 각각 1인 그룹, 2인 그룹, 3인 그룹으로 나눠서 생각할 수 있다
// 따라서 3 * 2!이 전체 경우의 개수다
const factorial = (n) => {
if (n <= 1) return n;
return n * factorial(n - 1);
};
// 발표순서 담을 변수를 선언한다
let order = 0;
// 어떠한 조가 이미 포함되었는지 확인하기 위해 isUsed 배열을 생성
// Array(N+1)인 이유는, 조는 1조부터 시작하지만 배열 인덱스는 0부터 시작하기 때문에 더미데이터를 앞에다 넣어주는 것
const isUsed = Array(N + 1).fill(false); // 결과는 [false, false, false, false]
// K의 개수만큼 반복
for (let i = 0; i < K.length; i++) {
// K의 i번째 조를 num에 담는다.
const num = K[i];
// 1R: num = K[0] = 2
// 2R: num = k[1] = 3
// 3R: num = K[2] = 1
// 사용했는지 판별하기 위하여 isUsed에 true로 값을 바꿈
isUsed[num] = true;
// 1R: isUsed[2] = true, [false, false, true, false]
// 2R: isUsed[3] = true, [false, false, true, true]
// 3R: isUsed[1] = true, [false, true, true, true]
// 아래 코드는 해당 숫자보다 앞에있는 경우를 구해주는 식이다
const candidates = isUsed.slice(1, num);
// 1R: candidates = isUsed.slice(1, 2) = [false];
// 2R: candidates = isUsed.slice(1, 3) = [false, true]
// 3R: candidates = isUsed.slice(1, 1) = []
const validCnt = candidates.filter((el) => el === false).length;
// 1R: validCnt = [false] 에서 false 의 length = 1
// 2R: validCnt = [false, true]에서 false 의 length = 1
// 3R: validCnt = 0
const formerCnt = validCnt * factorial(N - i - 1);
// 1R: formerCnt = 1 * factorial(3-0-1) = 1 * 2! = 2
// 2R: formerCnt = 1 * factorial(3-1-1) = 1 * 1 = 1
// 3R: formerCnt = 0
order = order + formerCnt;
// 1R: order = 0 + 2 = 2
// 2R: order = 2 + 1 = 3
// 3R: order = 3 + 0 = 3
}
return order; // 3
}한 줄 평
.fill()함수에 대해 알았다. 방문체크 알고리즘에 자주 쓰이는 메써드로 해당 그룹/카테고리 전체를 체크할 수 있다. 인덱스가 0부터 있는 배열의 경우 더미데이터를 만들어야하기 때문에,Array(N + 1).fill(false)로 만들어야하는게 포인트arr.fill(value[, start[, end]])value: 배열 채울 값start: 시작 인덱스, 기본 값은 0end: 끝 인덱스, 기본 값은this.length
참고링크 https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/fill
oneThing