[programmers] 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839

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

 

 

문자열의 최대 길이가 7이므로, 

7개의 문자로 만들 수 있는 최대 문자열의 수 7! ≒ 5000

문자의 개수가 N일 때 만들 수 있는 문자열의 길이는 1,2,3,,,N 이므로만들 수 있는 문자열의 최대 개수는 약 10000 라고 할 수 있음(어림잡음..)

 

 

더하여 모든 문자열에 대해 소수임을 판별해야 하는데

이는 소인수분해 방식을 통해 √N 번의 연산으로 해결 가능하며...

(1~√N까지의 수로 나눈 나머지를 구해본 후 나머지 숫자들은 생략)

방식은 다음과 같다

 

    private static boolean isPrime(String number) {
        int N = Integer.valueOf(number);
        if (N == 0 || N < 2) return false;

        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (N % i == 0) {
                return false;
            }
        }
        return true;
    }

 

 

(+ 2의 배수인 경우를 처음에 제한 후, for문에서 +=2씩 증가시켜 연산하는 방식도 가능함)

 

 

 

 

따라서 순열 함수를 이용하여 자릿수를 선택 후, 만들어진 수에 대하여 소수인지를 검사 후, set 자료형에 삽입하는 방식으로 중복을 제거하며 문제를 풀이함.

 

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution{
    static Set<Integer> set = new HashSet<>();
    static boolean[] isChecked;
    public static int solution(String numbers) {
        int answer = 0;

        int length = numbers.length();
        char[] nums = new char[length];
        nums = numbers.toCharArray();
        isChecked = new boolean[length];

        String s;
        int i=1;        //만들어야 하는 문자열 길이
        while (i <= length) {
            for (int starti = 0; starti < length; starti++) {
                s=String.valueOf(nums[starti]);
                isChecked[starti]=true;

                permutation(s, nums, i);
                Arrays.fill(isChecked, false);
            }
            i++;
        }
        answer = set.size();
        return answer;
    }

    private static void permutation(String s, char[] nums, int len) {

        if (s.length() == len) {
            if (isPrime(s)) set.add(Integer.valueOf(s));
            return;
        }

        String curString;
        for (int i = 0; i < nums.length; i++) {
            if (isChecked[i]) continue;
            //선택 가능
            isChecked[i] = true;
            curString=s.concat(String.valueOf(nums[i]));
            permutation(curString, nums, len);
            isChecked[i] = false;
        }

    }

    private static boolean isPrime(String number) {
        int N = Integer.valueOf(number);
        if (N == 0 || N < 2) return false;

        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (N % i == 0) {
                return false;
            }
        }
        return true;
    }
}