[JAVA] 순열 - 경우의 수 모두 구하기

I / O

I 1 :  첫 자리수가 1이고, 0과 1로만 구성된 서로다른 int가 들어있는 int형 배열

I 2 : 임의의 int N

I 3 : 임의의 int[ ] K  (K의 길이 = 뽑아야 할 갯수 = r 이라 하자)

O : ArrayList<int[ ]>

---

문제

: 1~N까지 N개의 숫자 중, r개를 나열하는 경우를 모두 ArrayList<int[ ]>에 담아 리턴하시오

---

사용한 템플릿 메서드, 문법

1. 팩토리얼( factorial )

2. 순열 (perm == permutation)

3. Arrays.toString( ) : 배열은 참조변수이기때문에 보기에 같아도 주소값이 다르다. 배열끼리 비교를 위해 사용.

4. .equals( ) : Arrays.toString( )과 같이 String타입을 비교할 때 사용. String은 참조변수이므로, == 사용 불가.

---

코드작성

코드 1) 위의 경우

import java.util.*;

/*
1. 1부터 N까지 n개의 수 중에서, r개를 뽑아 나열하는 경우를 모두 배열로 만듦
2. 찾은 배열중 지정한 배열과 일치하는 경우가 몇번째로 나온 경우인지 순서를 출력
 */

public class permutation4 {
    // 엔트리 포인트
    public static void main(String[] args) {
        int N = 3;
        int[] K = {2,3,1};

        // 결과 출력부분
        System.out.println(orderOfPresentation(N,K));
    }

    // 팩토리얼 메서드
    public static int factorial (int n) {
        if (n <= 1) return n; // 재귀 base 케이스. 즉, 1까지만 곱한단 소리
        else return factorial(n-1) * n; // 지금 수*하나 작은 수. 하나 작은 수는 다시 재귀로 하나 더 작은수로 곱을 반복
    }

    // permutation(순열) 메서드
    public static ArrayList<int[]> perm (ArrayList<int[]> list,boolean[] visited, int depth, int n, int r, int[] arr, int[] base) {
        // r개 뽑았을 때, list에 추가
        if(depth == r) {
            list.add(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, r, tempArr, base);
                visited[i] = false;
            }
        }

        // 최종 완성된 list 반환
        return list;
    }

    // 조건을 정하고, 지정배열과 순열로 나온 배열을 비교하는 메서드
    public static int orderOfPresentation(int N, int[] K) {
        // 총 순열 경우의 수
        int total = factorial(N);

        // 변수 선언부
        ArrayList<int[]> list = new ArrayList<>();
        boolean[] visited = new boolean[K.length];

        // 임의의 숫자 N까지의 숫자를 배열로 만듦
        int[] base = new int[N];
        for(int i=0 ; i<N ; i++) {
            base[i] = i+1;
        }

        // 순열로 된 ArrayList를 뽑아냄
        list = perm(list, visited, 0, N, K.length, new int[]{}, base);

        // 몇번쨰 순서인지 찾는 곳
        int num = 0;
        for (int i = 0; i < total; i++) {
            // 여기가 핵심. arr는 같은 형태라도 주소값이 서로다른 참조변수. 그냥 비교하면 주소값이 다르므로, Arrays.toString(arr)형식을 써야 안의 진짜 값을 비교할 수 있다.
            if(Arrays.toString(list.get(i)).equals(Arrays.toString(K))) num = i;
        }

        // 결과를 엔트리 포인트에 전달
        return num;
    }
}

 

코드 2) 멱집합 : String타입 순열 구하기

public class Solution { 
    public static ArrayList<String> powerSet(String str) {
        ArrayList<String> result = new ArrayList<String>();

        String [] arr = str.split("");

        List<String> strList = Arrays.asList(arr);
        ArrayList<String> list = (ArrayList<String>) strList.stream().distinct().sorted()
                .collect(Collectors.toList());

        final Stack<String> stack = new Stack<>();

        search(stack, 0, result, list);
        Collections.sort(result);
        
        return result;
    }


    private static void search(Stack<String> stack, int k, ArrayList<String> result, ArrayList<String> list) {
        if(k >= list.size()) {
            String temp = "";
            Stack<String> stack2 = new Stack<>();
            Stack<String> stack3 = new Stack<>();
            while(stack.size()!=0) {
                stack3.push(stack.peek());
                stack2.push(stack.pop());
            }
            while(stack3.size()!=0) stack.push(stack3.pop());
            while(stack2.size()!=0) temp += stack2.pop();

            result.add(temp);

        } else {
            stack.push(list.get(k));
            search(stack, k+1, result, list);

            stack.pop();
            search(stack, k+1, result, list);
        }
    }
}

---

실 사용 방법

1. 경우의 수를 구하는 search 메서드 : 그대로 사용

    private static void search(Stack<String> stack, int k, ArrayList<String> result, ArrayList<String> list) {
        if(k >= list.size()) {
            String temp = "";
            Stack<String> stack2 = new Stack<>();
            Stack<String> stack3 = new Stack<>();
            while(stack.size()!=0) {
                stack3.push(stack.peek());
                stack2.push(stack.pop());
            }
            while(stack3.size()!=0) stack.push(stack3.pop());
            while(stack2.size()!=0) temp += stack2.pop();

            result.add(temp);

        } else {
            stack.push(list.get(k));
            search(stack, k+1, result, list);

            stack.pop();
            search(stack, k+1, result, list);
        }
    }

2. 메인 메서드에서 search메서드 사용하기 : 변수(리터럴) 선언 및 search 돌리기

	public static void main () {
    	// 주어진 리터럴
        String str = "abcde";
        
        // 리터럴로 주어진 문자열을 분해해서 담은 Arraylist로 변환
    	ArrayList<String> list = new ArrayList<String>(Arrays.asList(str.split("")));
        
        // 모든 경우의 수를 담을 Arraylist
		ArrayList<String> result = new ArrayList<>();
        
        // list의 각 인자를 넣다뺄때 사용할 바구니 stack
        Stack<String> stack = new Stack<>();
        
        // 위에서 선언한 리터럴들을 넣고 돌림. 0은 index 0번째부터 시작한다는 뜻
        search(stack, 0, result, list);        
        
        // 모든 부분집합이 담겨서 출력된다
        System.out.println(result);
    }

 

 

참고링크 : 순열과 조합