Factorial 통한 발표순서 구하기 Javascript

cptkuk91·2022년 8월 2일
1

Algorithm

목록 보기
45/161

문제

조의 수 N과 발표 순서 K가 있을 때 K 순서가 몇 번째 경우의 수인지 구하기

경우의 수를 구할 수 있는 factorial

function factorial (n) {
	if(n <= 1){
    	return 1;
    } else {
    	return n * factorial(n - 1);
    }
}

문제의 핵심

단순히 경우의 수를 구하는 문제가 아니라 K 순서가 몇 번째 수인지를 구해야한다.

flag를 통해 배열을 false로 채워넣은 후, 지나오면서 true로 바꿔주고 false의 개수를 세는 방식을 사용하면 됩니다.

ex)

[false, false, false, false] 일 때 1개..
[false, false, false, true] 가 됐을 경우 아직까지 2개
[false, false, true] 가 됐을 경우 3개
[false, true] 가 됐을 경우 4개.. 이런식으로 계속해서 true로 바뀌는 경우 filter를 통해 제외 시켜 버리고 .length 를 붙여 숫자를 구할 수 있다.

코드

function solution(N, K) {
	let result = 0; // 몇 번째 수인지 결과값을 담아줄 곳
    
    // factorial 만들어주기
    const factorial = (n) => {
    	if(n <= 1){
        	return 1;
        } else {
        	return n * factorial(n - 1);
        }
    }
    
    // N + 1 한 이유는 0조가 없다.
    const flag = Array(N + 1).fill(false);
    
    for(let i = 0; i < K.length; i++){
    	let inputNum = K[i];
        flag[inputNum] = true; // 숫자를 체크하면서 flag로 바꿔준다.
        const waitingNum = flag.slice(1, inputNum).filter((el) => el === false).length; // 요소값이 false 경우 카운트 하자.
		const cnt = waitingNum * factorial(N - i - 1);
        result += cnt;
    }
    return result;
}

가장 쉽게 설명했다고 생각하는 블로그: https://wnsdufdl.tistory.com/77

profile
메일은 매일 확인하고 있습니다. 궁금하신 부분이나 틀린 부분에 대한 지적사항이 있으시다면 언제든 편하게 연락 부탁드려요 :)

0개의 댓글