[Java] 브루트포스(순열과 조합 구현) JAVA

 브루트포스 알고리즘 문제에서 순열과 조합문제가 자주 등장해서 자바로 구현한 것을 코드로 정리해 놓으려고 한다.

 

 순열과 조합을 구현하는 방법은 백트래킹 개념을 이용하여 크게 2가지가 있는데, 첫번째는 Swap을 이용한 방법과, Visited배열을 이용한 2가지 방법이 있다.

 

나는 visited배열을 이용한 구현이 더 편리해서 visited배열을 이용한 백트래킹으로 4가지(순열, 중복순열, 조합, 중복조합)경우를 정리하려고 한다. visited배열은 중복처리를 체크할 목적으로 사용되며 중복을 허용할 경우 필요없게 된다.

 

 Swap과 Visited 방법 중 어느 방법이 성능적으로 더 효율적인지는 체크해보지 않았다. 문제를 풀다가 Swap방법이 꼭 필요한 경우가 있다면 그때 따로 정리하려고 한다. (성능은 비슷하다고 한다.)

 

+ 이해하기 힘들었지만, 정리할 때는 완벽하게 이해를 했다. 하지만 나중에 까먹을거 같으니 직접 구현해보는 복습을 충분히 해둬야할 것 같다.

 

변수	설명
String str	주어진 조건(필요시 배열로 처리) ex) "12345"
int r	주어진 조건에서 선택 할 개수 ex) 5개중 2개를 뽑는다. r = 2
List<Integer> list	각 경우를 저장할 리스트
boolean[] visited	순열과 조합에서 주어진 조건 중 중복해서 뽑지않게 체크용도 (중복을 허용할 시 필요없음)
String temp	각 상황마다 뽑힌 것들을 임시로 저장할 변수(필요시 배열로도 가능)
int count	각 상황의 결과의 개수가 몇개인지 확인할 용도(없어도 됨)

 

 

1. 순열

//순열
static void perm(String str, String temp, int r){
    if (r == 0) {
        int num = Integer.parseInt(temp);
        list.add(num);
        count++;
        return;
    }

    for (int i = 0; i < str.length(); i++) {
        if(!visited[i]){
            temp += str.charAt(i);
            visited[i] = true;
            perm(str, temp, r - 1);
            visited[i] = false;
            temp = temp.substring(0, temp.length() - 1);
        }
    }
}

 

 

2. 중복순열

//중복순열
static void dupPerm(String str, String temp, int r) {
    if (r == 0) {
        int num = Integer.parseInt(temp);
        list.add(num);
        count++;
        return;
    }

    for (int i = 0; i < str.length(); i++) {
        temp += str.charAt(i);
        dupPerm(str, temp, r - 1);
        temp = temp.substring(0, temp.length() - 1);
    }
}

 

 

3. 조합

//조합
static void comb(String str, String temp, int start, int r) {
    if (r == 0) {
        int num = Integer.parseInt(temp);
        list.add(num);
        count++;
        return;
    }

    for(int i=start; i<str.length(); i++){
        if(!visited[i]){
            temp += str.charAt(i);
            visited[i] = true;
            comb(str, temp, i + 1, r - 1);
            visited[i] = false;
            temp = temp.substring(0, temp.length() - 1);
        }
    }
}

 

 

4. 중복조합

//중복조합
static void dupComb(String str, String temp, int start, int r) {
    if (r == 0) {
        int num = Integer.parseInt(temp);
        list.add(num);
        count++;
        return;
    }

    for(int i=start; i<str.length(); i++){
        temp += str.charAt(i);
        dupComb(str, temp, i, r - 1);
        temp = temp.substring(0, temp.length() - 1);
    }
}

 

 

+ 전체 소스코드

import java.util.*;


public class TestFree {

    static boolean[] visited;
    static List<Integer> list = new ArrayList<>();
    static int count = 0;

    public static void main(String[] args) {
        //문자열 str 요소중 r개의 순열 or 중복순열 or 조합 or 중복조합 원소들을 모두 List에 담기
        String str = "12345";
        visited = new boolean[str.length()];
        
        dupComb(str, "",0,3);
        System.out.println(list);
        System.out.println("count : " + count);
    }

    //순열
    static void perm(String str, String temp, int r){
        if (r == 0) {
            int num = Integer.parseInt(temp);
            list.add(num);
            count++;
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            if(!visited[i]){
                temp += str.charAt(i);
                visited[i] = true;
                perm(str, temp, r - 1);
                visited[i] = false;
                temp = temp.substring(0, temp.length() - 1);
            }
        }
    }

    //중복순열
    static void dupPerm(String str, String temp, int r) {
        if (r == 0) {
            int num = Integer.parseInt(temp);
            list.add(num);
            count++;
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            temp += str.charAt(i);
            dupPerm(str, temp, r - 1);
            temp = temp.substring(0, temp.length() - 1);
        }
    }

    //조합
    static void comb(String str, String temp, int start, int r) {
        if (r == 0) {
            int num = Integer.parseInt(temp);
            list.add(num);
            count++;
            return;
        }

        for(int i=start; i<str.length(); i++){
            if(!visited[i]){
                temp += str.charAt(i);
                visited[i] = true;
                comb(str, temp, i + 1, r - 1);
                visited[i] = false;
                temp = temp.substring(0, temp.length() - 1);
            }
        }
    }

    //중복조합
    static void dupComb(String str, String temp, int start, int r) {
        if (r == 0) {
            int num = Integer.parseInt(temp);
            list.add(num);
            count++;
            return;
        }

        for(int i=start; i<str.length(); i++){
            temp += str.charAt(i);
            dupComb(str, temp, i, r - 1);
            temp = temp.substring(0, temp.length() - 1);
        }
    }

}