[JAVA] powerSet (멱집합)

멱집합

: 주어진 집합의 모든 부분집합들로 구성된 집합

 

---

 

 

 

문제

특정 문자열에 포함된 문자를 정렬하고, 중복없이 구할 수 있는 조합을 구하시오

즉, 

1. 문자열의 중복을 제거

2. Sort

3. 조합을 구하기 (멱집합)

---

풀이 1) 멱집합 공식 없이 구해보기 (실패)

: 모든 멱집합을 구하려면 하나하나 for문을 추가해줘야 한다.(사실상 불가능)

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public static void main(String[] args) {
        String str = "jump";
        System.out.println(powerSet(str));
    }


    public static ArrayList<String> powerSet(String str) {
        // TODO:

        // for문으로 0번째 인텍스~ str.length-1번째 인덱스까지 길이의 문자열을 ArrayList에 넣어줌
        ArrayList<String> List = new ArrayList<>();
        List.add("");
        String [] arr = str.split("");
        List<String> strList = Arrays.asList(arr);

        List<String> stList = strList.stream().distinct().sorted()
                .collect(Collectors.toList());


        for (int i=0 ; i<stList.size() ; i++) {
            String a = stList.get(i);
            List.add(a);
            for(int k=1 ; k<stList.size() ; k++) {
                for (int j = k; j < stList.size() - i; j++) {  // <= 순회 수정하기 , 첫 순회만 해버림..
                    a += stList.get(i + j);
                    List.add(a);
                }
                a=stList.get(i);
            }
        }
        return List;
    }
}

 

---

 

풀이 2) 멱집합(powerSet) 공식을 통해 구하기

: 재귀 메서드를 통해 구하는 방법

: ArrayList로 반환하기 위해, 재귀메서드의 base code부분에서 비효율적인 연산이 추가되었다.(stack질)

: 풀이 코드 구현

import java.util.*;
import java.util.stream.Collectors;

public class powerSet {

    public static void main(String[] args) {
        String str = "acdeeeb";

        System.out.println(powerSet(str));
    }

    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);
        }
    }
}

 

: 주석이 붙은 코드

import java.util.*;
import java.util.stream.Collectors;

public class powerSet {

    // IntelliJ에서 돌려보기위한 엔트리 포인트. str은 임의로 넣었다.
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("아무 문자열을 입력하고, Enter를 누르시오.");
        String str = scanner.nextLine();

        // 결과값 확인용 출력
        System.out.println(powerSet(str));
    }

    // 재귀를 돌리기 위한 준비단계 함수. 멱집합을 ArrayList형태로 받을 것이다
    public static ArrayList<String> powerSet(String str) {
        // 결과값인 멱집합 경우의 수 전체를 담을 ArrayList<String>
        ArrayList<String> result = new ArrayList<String>();

        // 입력받은 str을 한 글자씩 나누어 중복제거 및 sort해줄 과정
        String [] arr = str.split("");
        List<String> strList = Arrays.asList(arr);
        ArrayList<String> list = (ArrayList<String>) strList.stream().distinct().sorted()
                .collect(Collectors.toList());

        // 재귀문에서 나눠진 문자열을 부분집합의 요소로 담아줄 stack(바구니)
        final Stack<String> stack = new Stack<>();

        // 재귀 시작. 파라미터 : str을 담아줄 stack, list의 0번째 인덱스부터 시작할것이므로 0, result.add()로 부분집합을 받아줘야 하므로 넣음, 요소를 뽑아낼 목록인 list도 필요
        search(stack, 0, result, list);
        // search로 반환된 ArrayList는 긴것부터 뒤죽박죽으로 반환되므로, sort 필요
        Collections.sort(result);

        // 최종반환이라 봐도 됨(여기선 main메서드에 전달하고, main에서 최종 출력)
        return result;
    }

    // 리턴이 필요하지 않으므로 void 타입 (어차피 result에 add로 다 보낼것이므로)
    private static void search(Stack<String> stack1, int k, ArrayList<String> result, ArrayList<String> list) {
        // base case. 즉, 요소의 index는 list의 길이 -1까지이므로, 거기까지 반복.
        if(k >= list.size()) {
            // 임시 string. 한 글자씩 떼어진 stack안의 요소를 하나로 합쳐주기 위한 임시 string
            String temp = "";
            // stack으로 작업치기위해 stack 두개 더 필요함
            Stack<String> stack2 = new Stack<>(); // 거꾸로 된 순서의 배열을 반듯하게 저장하기위해 담는 stack
            Stack<String> stack3 = new Stack<>(); // stack1에서 stack2로 보내기만 하면 재귀가 안되므로, stack2에 보내고 나서, 다시 stack1에 채워주기 위해 요소를 임시로 담는 stack
            // stack1의 요소를 순서대로 만들기 위한 반복작업. 그렇다고 stack1의 순서가 훼손되면 안되므로, 일단 stack3에도 임시저장
            while(stack1.size()!=0) {
                stack3.push(stack1.peek()); // 임시저장(값의 복제라고 봐도 된다)
                stack2.push(stack1.pop()); // stack1을 비움과 동시에 stack2에 다시 쌓는 과정
            }
            while(stack3.size()!=0) stack1.push(stack3.pop()); // stack3에 임시저장한거 다시 stack1에 넣어주는 작업
            while(stack2.size()!=0) temp += stack2.pop(); // stack2에 바르게 쌓아놓은 것을 문자열로 바꿔주는 작업

            result.add(temp); // 바른 순서로 만든 문자열(하나의 경우의 수)을 result에 저장하는 작업

        } else {
            // k번째 인덱스에 해당하는 값을 포함한 경우의 수를 구하는 과정
            stack1.push(list.get(k));
            search(stack1, k+1, result, list);

            // k번째 인덱스에 해당하는 값을 제외한 경우의 수를 구하는 과정
            stack1.pop();
            search(stack1, k+1, result, list);
        }
    }
}

 

 

---

멱집합 공식 기본코드

기본코드 1) 주어진 배열의 경우의 수 구하기

참고자료 : [Java]부분 집합(Subset)과 멱집합(Power Set)

import java.util.Arrays;

public class PowerSet_Combination {
    static int[] nums = { 1, 2, 3 };
    // 최대 원소의 개수
    static int max_cnt;
    // 각 부분 집합을 저장할 배열
    static int[] subset;

    public static void main(String[] args) {
        // 원소를 선택하는 개수 0 ~ 3개.
        for (int i = 0; i <= 3; i++) {
            max_cnt = i;
            subset = new int[i];
            // 대상 집합에서 원소를 0 ~ 3개를 선택하는 조합을 모두 구한다.
            Combination(0, 0);
        }
    }

    private static void Combination(int cnt, int k) {
        // 베이스코드
        if (cnt == max_cnt) {  
            System.out.println(Arrays.toString(subset));
            return;
        }
        // 재귀 메서드 => 29번줄 코드를 통해 파라미터값을 변경하며 재귀함수가 진행된다
        for (int i = k; i < nums.length; i++) {
            subset[cnt] = nums[i];
            Combination(cnt + 1, i + 1);
        }
    }
}

 

기본코드 2) 주어진 숫자까지의 조합의 경우

참고자료 : Java 멱집합 구하기 (PowerSet)

import java.util.Stack;

public class PowerSet {
    private static int n = 5;

    public static void main(String[] args) {
        final Stack<Integer> stack = new Stack<>();
        search(stack, 1);
    }

    private static void search(Stack<Integer> stack, int k) {
        if(k >= n + 1) {
            System.out.println(stack.toString()); // 부분 집합을 출력한다.
        } else {
            // 1. k를 부분집합에 포함한다.
            stack.add(k);
            search(stack, k + 1);

            // 2. k를 부분집합에 포함하지 않는다.
            stack.pop();
            search(stack, k + 1);
        }
    }
}

 

기본코드 2) 주어진 Character의 경우의 수 구하기 (내 코드 응용)

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class powerSetVerChar {
    private static final char[] characters = {'A', 'B', 'C', 'D', 'E'};

    public static void main(String[] args) {
        final Stack<Character> stack = new Stack<>();
        ArrayList<String> result = new ArrayList<>();

        search(stack, 0, result);

        Collections.sort(result);
        System.out.println(result);
    }

    private static void search(Stack<Character> stack, int k, ArrayList<String> result) {
        if(k >= characters.length) {
            String temp = "";
            Stack<Character> stack2 = new Stack<>();
            Stack<Character> 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(characters[k]);
            search(stack, k+1, result);

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