멱집합 심화

문제 

말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.

선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.

김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.

총 조의 수 N과 선생님이 말씀하시는 발표 순서 K가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.

모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다. ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

 

문제 요약

N 만큼의 요소를 가진 배열의 멱집합을 구하고 해당 멱집합에서 배열 K와 일치하는 배열이 몇 번째 경우의 수인지를 구해야 한다.

 

 

문제 풀이

처음 문제를 보았을땐 풀이가 어렵지 않았다. 그저 멱집합을 구하고 배열 K와 비교하여 해당 멱집합에서 같은 배열의 순번을 리턴하면 되었으나, 문제는 멱집합을 재귀를 통해 구하고 배열K와 모든 멱집합의 요소들을 반복문을 통해 비교하게되어 배열의 요소가 많아질 경우 계속해서 타임아웃에 걸렸다.

 

고민 해본 결과, 굳이 멱집합을 구할 필요가 없었다. 해당 문제에서 구해야 될건 특정한 배열이 아니라 해당 배열의 순번이며 멱집합의 순서도 오름차순으로 주어저 있기에 주어진 배열 K가 몇번째 경우의 수인지만 계산해내면 되었다.

 

 

예를 들어 배열 N =3이되면 멱집합은 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]가 된다. 여기서 K가 [2,3,1] 이라면 반환값은 3(인덱스)이 되면 된다.

 

여기서 배열의 첫번째 인덱스가 2가 될 경우의 수는 3번째와 4번째이다. 즉 2의 이전숫자인 1이 될 경우의 수를 모두 건너뛰고 2가 된 3번째와 4번째 배열에서 다음 인덱스가 올 경우의 수를 똑같이 구해주면 된다. 

 

그럼 다음 2번째 인덱스는 1 혹은 3이 된다. 우리가 구해야될 배열은 2번째 인덱스가 3인 배열이므로, 만약 2번째 인덱스가 1인 배열은 모두 건너뛰어주고 3인 배열의 순서를 반환하면 된다. 

 

 

class Solution {

    public int orderOfPresentation(int N, int[] K) {
        int result = 0;
        ArrayList<Integer> arr = new ArrayList<>(); // 연산이 끝난 자릿수의 값을 담음

        for(int i=0; i<K.length; i++){
            int value = K[i]; // 배열의 현재 인덱스의 실제 넘버
            int count = value-1; // 현재 자릿수에 대한 경우의 수
            int calculated = 1; // 현재 자릿수 이후의 모든 경우의 수

            //해당 자릿수의 경우의 수
            for(int j=K.length-i-1; j>1; j--){
                calculated *=j;
            }

            //현재 자릿수의 값보다 낮은 값이 소모 됬는지 체크
            //낮은 값이 소모 됬다면 그만큼의 경우의 수를 차감해주어야됨
            for(int value2 : arr){
                if(value>value2) count --;
            }
            
            result += count*calculated; //해당 수만큼의 경우의수를 건너뜀
            
            arr.add(value); // 소모된 값은 다음 계산을 위해 배열에 추가 
        }
        return result;
    }
}

1. 현재 인덱스 이후의 인덱스부터의 모든 경우의수를 구한다.
2. 구한 값을 현재 인덱스 -1 만큼 곱해준다. (-1을 해주지 않으면 현재 인덱스를 건너뛴 상태가 된다.)
3. 이때 이전 인덱스의 숫자들이 현재 인덱스의 숫자보다 작을경우 그 수만큼 차감하여 처음 구한 경우의 수를 곱해줘야 한다.

 

 

마무리

최대한 풀어 설명하려 했지만 도무지 더이상 쉽게 설명이 안된다...

다음에 봤을땐 이해가 안될것 같지만 혼자 풀었다는 것에 위안을 삼자...