[Java] [소수찾기] 소수구하기/순열/조합

소수 구하기

• 11을 소수판별 하기 위해서는 2에서 11의 제곱근까지만 확인해보면 된다. ★
• 49와 같이 n^2 의 경우 제곱근 7까지 탐색
• for ( int i=2; i*i<=num; i++)

public static boolean decimal(int num){
        if(num<=1) return false;
        for(int i=2; i*i<=num; i++){
            if(num%i==0) return false;
        }
        return true;
}

순열(Permutation) 구하기 : nPr 

• n개의 카드에서 1~r 개를 순서있게 뽑을수 있는 조건
• Backtracking 으로 구현시,  r-1 값을 넘겨주며, r=0일때 탈출조건 필요. 

import java.util.ArrayList;
public class Solution {
	public static void main(String[] args) {
		
		int[] arr = {1,2,3};
		boolean[] visited = new boolean[arr.length];
		
		//순열구하기 백트래킹
		for (int r = 1; r <= arr.length; r++) {
			System.out.println("=== "+r+"개 뽑기 ===");
			perm("", arr, visited, r);
		}
	}
	
	public static void perm(String str, int[] arr, boolean[]visited, int r) {
		if(r == 0) {
			System.out.println(str);			
			return;
		}else {
			for(int i = 0; i< arr.length; i++) {
				if(!visited[i]) {
					visited[i] = true;
					perm(str+Integer.toString(arr[i]), arr, visited, r-1);
					visited[i] = false;
				}				
			}
		}		
	}
}

조합(Combination) 구하기 : nCr

• n개의 카드에서 1~r 개를 순서없이 뽑을수 있는 조건.
• start 변수를 두어, start 오른쪽에 있는 카드만 뽑도록 하여 중복 방지
• 나머지는 순열과 동일

import java.util.ArrayList;
public class Solution {
	public static void main(String[] args) {
		
		int[] arr = {1,2,3};
		boolean[] visited = new boolean[arr.length];
		
		//조합구하기 백트래킹
		for (int r = 1; r <= arr.length; r++) {
			System.out.println("=== "+r+"개 뽑기 ===");
			comb(arr, visited, 0, r);
		}
	}
	public static void comb(int[] arr, boolean[]visited, int start, int r) {
		if(r == 0) {
			// post_work //
			for (int i = 0; i < arr.length; i++) {
				if(visited[i]) System.out.print(arr[i]+" ");
			}
			System.out.println();
			////
			return;
		}else {
			for(int i = start; i< arr.length; i++) {
				visited[i] = true;
				comb(arr, visited, i+1, r-1);
				visited[i] = false;
			}
		}		
	}
}

 

프로그래머스 - 소수찾기

import java.util.*;
class Solution {
    
    static int answer = 0;
    static ArrayList<Integer> arr = new ArrayList<Integer>();

    public int solution(String numbers) {
                 
        //순열 구하기 : nPc
        boolean[] visited = new boolean[numbers.length()];
        for(int r=1; r <=numbers.length(); r++){            
            perm("",numbers, visited, r);
        }
        
        return answer;
    }
    
    //순열 구하기
    public static void perm(String str, String numbers, boolean[] visited, int r){
        if(r==0) {
            int num = Integer.parseInt(str);
            if(decimal(num) && !arr.contains(num)){
                arr.add(num);
                answer++;
            }            
        }
        for(int i=0;i<numbers.length();i++){            
            if(!visited[i]){
                visited[i] = true;                
                perm(str+numbers.charAt(i), numbers, visited, r-1);
                visited[i] = false;    
            }
        }      
    }
    
    //소수구하기
    public static boolean decimal(int num){
        if(num<=1) return false;
        for(int i=2; i*i<=num; i++){
            if(num%i==0) return false;
        }
        return true;
    }
}