[완전탐색, 소수, 순열] level2 프로그래머스 소수 찾기 자바 풀이

프로그래머스 소수찾기 자바(java) 풀이

• Level 2
• 완전 탐색
• 소수 찾기
  
  
  

문제 정리

1. 한자리 숫자가 적힌 종이가 있다.
2. 종이 조각으로 만들 수 있는 소수가 몇 개 인지 return 하여라.
3. 입력으로 주어지는 numbers는 길이 1 이상 7 이하의 문자열이다.
   
   
   

문제 풀이

numbers를 파싱하여 이용해서 만들 수 있는 모든 수를 만든 후 소수인지 확인합니다.

1. 모든 순열을 확인합니다. n개의 수중 1,2,3..n개를 뽑는 모든 순열을 구합니다.
2. 구한 문자를 숫자로 바꾸어 소수인지 판단합니다. 소수라면 set에 저장합니다. set에 저장하는 이유는 중복된 숫자를 방지하기 위함입니다.
3. 소수인지 판단은 그 수의 루트값 까지 나눠보면 알 수 있습니다.
   
   
   

순열(Permutaion)

오랜만에 순열을 구현하려니 생각이 안나서 헤맸다 ㅠㅠ 다시 정리하자!!

1. 순열을 담을 배열을 static으로 select 배열을 선언한다
2. visited 배열을 N 크기로 선언한다(boolean)
3. perm 함수를 작성한다 perm(int start, int r, int n)
4. start를 0부터 증가시키면서 select 배열에 순차적으로 넣습니다. visited도 방문처리 해줍니다.
5. 재귀적으로 perm(start+1, r, n)을 호출합니다.
6. start가 r이 될때까지 즉 r개의 수를 뽑아 순열을 만듭니다
   
   
   

프로그래머스 level2 소수 찾기

import java.io.IOException;
import java.util.HashSet;
 
public class Main {    
    public static void main(String[] args) throws IOException {
        System.out.println(solution("17"));
        System.out.println(solution("011"));
    }
    
    /*
     * 한자리 숫자가 적힌 종이 조각이 있음
     * 흩어진 종이 조각을 붙여 소수를 몇개 만들 수 있는가?
     * 최대 7자리 수 소수
     * 최대 7! 가지수 이므로 모두 해본다
     * 그리고 소수인지 판단하며 된다.
     */
    
    
    static char[] chs;
    static boolean[] visited;
    static HashSet<Integer> set;
    public static int solution(String numbers) {
        int len = numbers.length();
        
        visited = new boolean[len];
        set = new HashSet<>();
        
        for(int i=1; i<=len; i++) {
            chs = new char[i];
            perm(0, i, len, numbers);     
        }
        
        return set.size();
    }
    
    public static void perm(int start, int r, int n, String numbers) {
        if(start == r) {
            // chs[0]이 0이면 안됨
            if(chs[0] == '0') return;
            
            // 숫자로 변환
            int num = Integer.parseInt(String.valueOf(chs));
            
            if(isPrimeNumber(num)) {
                set.add(num);
            }
            return;
        }
        
        for(int i=0; i<n; i++) {
            if(visited[i]) continue;
            
            visited[i] = true;
            chs[start] = numbers.charAt(i);
            perm(start+1, r, n, numbers);
            visited[i] = false;
        }
    }
    
    public static boolean isPrimeNumber(int num) {
        if(num == 1) return false;
        
        for(int i=2; i<=Math.sqrt(num); i++) {
            if(num % i == 0) return false;
        }
        return true;
    }
    
}