[프로그래머스 (Java)] 소수찾기

 

https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 

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

1. IsPrime(number)

에라토스체네스의 체를 이용한 소수찾기 메서드 입니다

2 ~ 루트n 까지의 숫자를 돌면서 n 을 나눌 수 있는지 확인합니다.

만약 2 로 n 을 나눌 수 없다면 n 은 소인수로 2 를 가지지 않는다는 것을 의미합니다.
또한 2의 모든 배수는 소수가 아니기 때문에 2 ~ 루트n 까지의 모든 2의 배수는 나눠지는지 확인해보는 후보에서 제거합니다.

[출처] 에라토스체네스의체 위키피디아 

2. findAllNumber()

입력받은 문자열에서 조합할 수 있는 모든 문자열을 생성하여 Set 에 저장합니다. 

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

class Solution {
    public boolean isPrime(int number) {
        if (number == 0 || number == 1) return false;

        int sqrt = (int) Math.sqrt(number);
        // candidate 은  처음에 0 으로 초기화 된다. 1 ~ sqrt 까지 check (index 는 0 ~ sqrt-1)
        int[] candidate = new int[sqrt];
        for (int i = 1; i < sqrt; i++) {
            // 아직 접근이 안된 경우
            if (candidate[i] == 0) {
                // 만약 나눠지면 바로 return
                if (number % (i+1) == 0) {
                    return false;
                } else {
                    // i 부터 배수 전부 업데이트
                    for (int j = i; j < sqrt; j += (i + 1)) {
                        candidate[j] = (i + 1);
                    }
                }
            }
        }
        return true;
    }

    public void findAllNumber(Set<Integer> numberSet, String comb, String other) {
        if (comb != "") {
            numberSet.add(Integer.valueOf(comb));
        }
        for (int i = 0; i < other.length(); i++) {
            findAllNumber(numberSet, comb + other.charAt(i), other.substring(0, i) + other.substring(i + 1));
        }
    }

    public int solution(String numbers) {
        int answer = 0;
        Set<Integer> numberSet = new HashSet<>();
        findAllNumber(numberSet, "", numbers);
        for (Integer s : numberSet) {
            if (isPrime(s)) {
                answer++;
            }
        }
        return answer;
    }
}