[Algorithm] 프로그래머스 소수 찾기

코딩테스트 연습 - 소수 찾기

 

풀이

1. 주어진 문자열로 된 숫자에서 만들 수 있는 모든 숫자를 구함. (순열)

순열 알고리즘으로 가능한 모든 숫자를 만듦. 중복 가능성으로 Set에 저장하고 다시 리스트로 만듦.

 

2. 만들어진 숫자에 대해서 소수 판별 알고리즘 사용

소수 판별을 0과 1은 소수가 아니다.

2부터 숫자의 제곱근 까지의 수로 나눴을 때, 나눠떨어지지 않아야 한다.

 

전체 소스코드

import java.util.*;

class Solution {
    
    public Set<Integer> set = new HashSet<>();
    
    public void perm(String[] arr, int depth, int n, int r) {
        if (depth == r) {
            String tmp = "";
            for (int i = 0 ; i < r; i++) {
                tmp += arr[i];
            }
            set.add(Integer.parseInt(tmp));
        }
        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            perm(arr, depth+1, n, r);
            swap(arr, depth, i);
        }
    }
    
    public void swap (String[] arr, int depth, int i) {
        String tmp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = tmp;
    }
    
    public boolean isPrime(int number) {
        if (number == 0 || number == 1) return false;
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) return false;
        }
        return true;
    }
    
    public int solution(String numbers) {
        int answer = 0;
        String[] s = numbers.split("");
        
        for (int len = 1; len <= s.length; len++) {
            perm(s, 0, s.length, len);
        }
        
        
        List<Integer> list = new ArrayList<>(set);
        for (int i = 0 ; i < set.size(); i++) {
            int num = list.get(i);
            if (isPrime(num)) answer++;
        }
        
        return answer;
    }
}