[Programmers / Java] 소수 구하기(조합)

제목을 소수만들기 이지만 보다 집중한건 배열을 조합을 사용해 나누어 본것 입니다.

소수만들기

import java.util.ArrayList;
import java.util.List;

public class 소수_만들기 {

    static List<Integer> list = new ArrayList<>();

    public static boolean check(int num){
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }

    public static void combination(int arr[], boolean visited[], int start, int n, int r){

        if(r == 0){
            int result = 0;
            for (int i = 0; i < n; i++) {
                if(visited[i]){
                    result += arr[i];
                }
            }
            System.out.println("result = " + result);
            list.add(result);
            return;
        }

        for(int i = start; i < n; i++){
            visited[i] = true;
            combination(arr, visited, i+1,n,r-1);
            visited[i] = false;
        }
    }
    public static void solution(int[] nums){
        int answer =0;
        boolean visited[] = new boolean[nums.length];
        combination(nums,visited,0,nums.length,3);

        for (Integer integer : list) {
            if(check(integer)){
                answer++;
            }
        }
        System.out.println("list = " + list);
        System.out.println("answer = " + answer);
    }

    public static void main(String[] args) {
        solution(new int[] {1,2,3,4});
        solution(new int[] {1,2,7,6,4});
    }
}

배열이 주어졌을 때 조합을 만드는 법을 알아봤습니다.

n개의 배열이 주어졌을 때 순서상관있도록 3개씩 뽑는 것이 어려웠습니다.

 

 

다른 combination() 예시로 설명하겠습니다.

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
        visited[i] = true;
        combination(arr, visited, i + 1, n, r - 1);
        visited[i] = false;
    }
}

combination()메서드를 보면 start 부터 시작합니다.

[1, 2, 3, 4]가 있다면 start는 1,2,3,4 순서대로 갈것입니다.

처음 combination은 1~4까지

2번째 combination은 2~4까지

3번째 combination은 3~4까지 진행합니다.

 

visited가 결국 3개의 조합이 되는 것입니다.

[1,2,3,4]는 for문을 돌면서

3번의 combination중첩이 쌓일것입니다.

combination(arr,visitied,2,1)
combination(arr,visitied,1,2)
combination(arr,visitied,0,3)

이 때 visited는

[true, true, true, false] 가 되면 if문에 걸리고 print를 할 것입니다. 그리고 return을 하기 때문에 combination(arr,visitied,2,1)부분은 사라집니다. 그리고 i=2이기 때문에 visitied[2]=false가 동작합니다.

 

그럼 visited는 [true,true,false,false] 가 됩니다.

 

for문은 아직 끝나지 않았습니다. i=3이 되면서 visited[3]=true가 됩니다. 그리고 r=0이 되면서 combination(arr,visitied,4,0)이 됩니다. 자. 이제 for문이 끝나고 combination(arr,visitied,2,1)이 끝났습니다.

 

visited 배열을 잘 보면 이해할 수 있습니다.

[false, false, false, false]
[true, false, false, false]
[true, true, false, false]
[true, true, true, false] < 출력
[true, true, false, false] 
[true, true, false, true] <출력
[true, false, false, false] 
[true, false, true, false] 
[true, false, true, true] <출력
[true, false, true, false] 
[true, true, false, true] <출력
[true, false, false, false] 
[true, false, false, true] 
[false, false, false, false] 

이 한 과정이 start =0, r = 3일 때 visited가 변하는 과정입니다.

[false, false, false, false]
[false, true, false, false]
[false, true, true, false]
[false, true, true, true] < 출력
[false, true, true, false]
[false, true, false, false]
[false, true, false, true]
[false, true, false, false]
[false, false, false, false]

이건 start=1, r=2일때 visited가 변하는 과정입니다.

[false, false, false, false]
[false, false, true, false]
[false, false, true, true]
[false, false, true, false]
[false, false, false, false]

이건 start=2, r=1일때 visited가 변하는 과정입니다.

[false, false, false, false]
[false, false, false, true]
[false, false, false, false]

이건 start=3, r=0일때 visited가 변하는 과정입니다.

 

이렇게 for문이 끝나게 됩니다. r=3으로 조정한 만큼 true가 3개이면 r==0이 되면서 그 때 visitied 가 true인 값들을 빼서 쓰면 됩니다.