주어진 길이 N의 배열이 있을 때, 그 배열의 가능한 모든 요소의 순서 조합을 생각했을 때,

몇 번째 배열인지를 구하는 문제

입출력 예시

3,[2,3,1] => 3
5,[1,3,2,4,5] => 6

내가 작성한 코드

function orderOfPresentation (N, K) {
    // TODO: 여기에 코드를 작성합니다.
    //문제 이해하기
    //N을 가지고 배열을 만들 수 있다. [1,2,3,...N]
    //이렇게 만든 배열에서 원소의 위치를 바꾸어서 가능한 한 모든 배열을 만든다.
    //그 배열들을 순서대로 정렬했을때, 배열 K가 몇 번째인지 구해야 하는 문제다.
    //배열 K를 순회해야 한다. K의 길이는 N이다.

    //배열에서 K[i]를 제외하고 나머지 배열을 이용하여 자리수를 바꾸었을 때,
		//만들 수 있는 배열의 수를 구하는 함수
    function factorial(n){
        if(n === 1) return 1;
        return n * factorial(n-1);
    } 
    //K[i]보다 작은 수의 개수를 구하는 함수
    function min(n,arr){
        let result= 0;
        for(let j = 0; j < arr.length; j++){
            if(arr[j] < n){
                result++;
            }
        }
        return result;
    }
//여기서부터 먼저볼것
//결과를 저장할 변수 선언
    let orderOfP = 0;
//주어진 배열 K에 대해 순회하여야 한다. 
    for(let i = 0; i < N; i++){
      //배열 K에 대해..K[i]가 최솟값일 경우 그 자리수에 대해서는 건너뛰고 다음 요소로 가서 검사한다.
      if(K[i] <= Math.min(...K.slice(i))){
          continue;
      }else{ //K[i]보다 더 작은 수가 있을 경우에는 더 작은 수들을 이용해서 만들 수 있는 배열의 수를 더한다.
          orderOfP += factorial(N - i - 1) * min(K[i],K.slice(i + 1))
      }
    }
    return orderOfP;
}

수도 코드

입출력 예시부터 먼저 이해가 필요하다.

입력값으로 5,[1,3,2,4,5]가 들어온 경우를 생각해보자. 왜 출력이 6(번째)이 되어야 할까? 가 수도코드를 작성하는 핵심이다.

주어진 배열의 첫번째 요소는 1이다. 즉, 주어진 배열에서 1보다 작은 숫자는 없으므로(1이 최솟값이므로)

1을 첫번째 요소로 하여 만들 수 있는 배열을 다 나열해보면 다음과 같다.

[1,2,3,4,5],[1,2,3,5,4],[1,2,4,3,5],[1,2,4,5,3],[1,2,5,3,4],[1,2,5,4,3]...[1,5,4,3,2]

너무 많아서 다 열거하지 못했지만 24개임을 알 수 있는데, 이는 순열을 통해서 구할 수 있었다.

1을 제외한 나머지 4개의 숫자를 나열하는 서로 다를 방법의 수를 구하는 것이다.

순열의 공식에 의해서 432*1 = 24임을 알 수 있다.

만약에 출력이 25여야 한다면, 주어진 배열은 [2,1,3,4,5] 이었을 것이다. 왜냐하면 2를 제외한 나머지 요소들 중에서 가장 작은 숫자가 1이기 때문에, 1을 첫번째 요소로 하여 가능한 모든 숫자를 나열해보면 24가지가 나오기 때문이다.

그렇다면 만약에 주어진 배열의 첫 요소가 3으로 시작했다면, 1을 첫번째 요소로 하는 배열과 2를 첫번째 요소로 하는 배열들의 개수를 알아야 한다. 즉 최소 24*2개임을 알 수 있다.