[orderOfPresentation] N개를 나열하는 경우 중 특정 조합의 순서값 구하기

문제

: 1부터 N까지의 숫자를 나열하는 조합 중, 특정 조합의 순서값 구하기

: 단, 조합의 순서는 0번째 부터 센다

 

---

풀이

1. 모든 조합을 구해서 그 중 해당 조합의 순서(인덱스)구하기 : 조합 내용을 구할 수 있으나 느림

  1) 1부터 N까지의 수가 순차적으로 들어간 배열 생성

  2) String 형식으로 각 조합이 들어갈 ArrayList 작성

  3) 각 조합 배합할 int[ ]타입 ArrayList 생성

  4) 방문확인용 boolean [ ]

  5) 조합기 돌림

  6) 비교용 배열도 String으로 비교할거니 String으로 변경

  7) 조합 들어있는 String리스트 순회하면서 비교. 발견시 멈춤.

 

2. 해당 조합의 순서값만 구하기 : 모든 조합의 내용은 알 수 없으나 빠름

  : 목표 배열의 인자를 0번 인덱스부터 차례로 체크하며, 앞에 올 수 있는 숫자들에서 구할 수 있는 경우의 수를

    모두 더해가며 순서값을 구하는 방법

---

깃 링크

https://github.com/PNUHCT/AlgorismStorage.git

---

나의 코드

import java.util.*;

// 모든 경우의 수를 구해서 비교하는 방식 (다 구하느라 시간복잡도가 오래걸림)
public class orderOfPresentation {
    public static void main(String[] args) {
        int[] N = {1, 2, 3};

        int a = orderOfPresentation(3, new int[]{2,3,1});
        System.out.println(a);
    }

    public static int orderOfPresentation(int N, int[] K) {
        // 조합뽑기용 메서드에 넣을 인자들 선언하는 부분
        int[] base = new int[N];
        for (int i = 1; i <= N; i++) base[i-1] = i;
        ArrayList<String> cases = new ArrayList<>();
        ArrayList<int[]> list = new ArrayList<>();
        boolean[] visited = new boolean[N];

        // 조합기 돌림
        perm(list, visited, 0, N, new int[]{},base, cases);

        // 조합 비교 부분
        String strK = Arrays.toString(K);
        int result = 0;        
        for (int i = 0; i < cases.size(); i++) {
            if(cases.get(i).equals(strK)) {
                result = i;
                break;
            }
        }
        
        // 반환
        return result;
    }

    // 조합기 부분
    public static ArrayList<int[]> perm (ArrayList<int[]> list, boolean[] visited, int depth, int n, int[] arr, int[] base, ArrayList<String> cases) {
        // r개 뽑았을 때, list에 추가
        if(depth == n) {
            list.add(arr);
            cases.add(Arrays.toString(arr));
            return list;
        }

        // 재귀로 순열의 경우 모두 검색
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                // arr는 특성상 추가가 안되므로, 새로 만들고 복붙해줘야함
                int[] tempArr = Arrays.copyOf(arr, arr.length+1);
                tempArr[tempArr.length - 1] = base[i];
                list = perm(list, visited, depth+1, n, tempArr, base, cases);
                visited[i] = false;
            }
        }
        return list;
    }
}

---

레퍼런스

import java.util.*;

// 순서값만 구하는 공식, 조합의 내용은 알 수 없으나, 순서값을 빠르게 구할 수 있음
public class reference {
    public static void main(String[] args) {
        int[] N = {1, 2, 3};
        int a = orderOfPresentation(3, new int[]{2,3,1});
        System.out.println(a);
    }

    // 순서 구하는 메서드
    public static int orderOfPresentation(int N, int[] K) {
        // 순서값
        int order = 0;
        // 처음엔 전부 false. 사용된 숫자의 위치는 true가 될 것임. 0번째 인덱스는 더미데이터(무시값)
        boolean[] isUsed = new boolean[N + 1];

        for (int i = 0; i < K.length; i++) {
            // num은 비교할 배열 K의 i번째 요소 값
            int num = K[i];
            // i번째 요소가 사용됬으므로, 해당 위치는 true로 변경
            isUsed[num] = true;
            // 더미 데이터를 제외한 업데이트된 isUsed[]에서, i번째보다 앞쪽까지만 복사. 즉, 앞에 들어갈 수 있는 경우의 수 구할 목적
            boolean[] candidates = Arrays.copyOfRange(isUsed, 1, num);
            // 순서대로 일 때, num보다 앞에 올 수 있는 숫자 개수 구하기. false만 세므로 사용 안한애만 셈. 그 갯수는 validCnt
            int validCnt = 0;
            for (boolean candidate : candidates) if (!candidate) validCnt++;
            // 사용안한 숫자들마다 가질 수 있는 조합의 경우의 수를 구함
            // 즉. 현재 숫자보다 앞에 올수 있는 숫자개수 * 그 숫자마다 가질 수 있는 경우의 수 중 이미 사용한 i개를 뺸 경우의 수
            int formerCnt = validCnt * factorial(N - i - 1);

            // 최종 반환할 순서값 order = 현재까지의 경우의 수 + 방금 구한 경우의 수
            order = order + formerCnt;
        }
        // 즉, 사용한 숫자들을 제외하고. 현재 지정된 값의 앞에 올 수 있는 경우의 수를 더하면 최종 순서값이 나옴
        // 이때, index는 0부터 시작이므로, order번째랑 같음
        return order;
    }

    // 팩토리얼 공식
    public static int factorial(int n) {
        if(n <= 1) return 1;
        return n * factorial(n - 1);
    }
}