모든 경우의 수 에서 몇 번째 경우냐!

박찬섭·2023년 7월 10일
0

알고리즘

목록 보기
7/15

입력

인자 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

function fact (num) {
        if(num<=1)return 1;
        return num*fact(num-1);
}

function orderOfPresentation (N, K) {
    let used = new Array(N+1).fill(0);
    let count = 0;
    for(let i = 0; i < K.length; i++) {
        used[K[i]] = 1;
        let scenario = used.slice(1,K[i]).reduce((acc,cur)=>{return cur === 0 ? acc+=1 : acc},0) * fact(N-i-1);
        count+=scenario;
    }
    return count
}

입력받은 N에 따라 사용 되었는지 아닌지를 확인하는 배열 생성
들어온 입력받은 K 배열에 길이만큼 반복문을 돌림

used[k[i]] = 1; //현재 값을 사용함 처리
let scenario = used.slice(1,K[i]).reduce((acc,cur)=>{return cur === 0 ? acc+=1 : acc},0) * fact(N-i-1);
//현재 검토하고 있는 K[i]의 값보다 이전에 K[i]값들, used에서 사용되지 않은 이전 K[i]값들
//used에서 사용되지 않은 이전 K[i]값들의 경우의 수 = fact(N-i-1);

이전에 경우의 수 들을 count에 누적시켜서 더해주면 count는 현재 입력받은 값이 몇번째 경우의 수에서 등장할지에 대한 값을 가짐

profile
백엔드 개발자를 희망하는

0개의 댓글