프로그래머스 - 소수 찾기 (Java, 백트래킹, 소수, 에라토스테네스의 체)

아이디어

백트래킹 + 에라토스테네스의 체

 

백트래킹

완전탐색, 순열, 조합 문제의 경우 백트래킹을 먼저 시도해보는 편이다. 

일반적인 dfs 알고리즘에 visit 체크를 앞, 뒤로 추가하여 중복 방문을 막는다.

딱히 종료 조건이랄 것도 없어서 종료 조건은 따로 주지 않았다.

 

에라토스테네스의 체

소수를 판정하기 위해서는 특정 수보다 작은 수들로 나누어 떨어지는지 확인한다.

하지만, 특정 수보다 작은 모든 수를 탐색하는 경우 시간초과가 발생할 수 있다.

그러므로 에라토스테네스 체 알고리즘을 따라서 제곱근까지만 탐색한다.

sqrt 사용 시 부동 소수점 오류가 날 수 있어서 역으로 생각하여  i * i 가 x보다 작거나 같은 경우까지 탐색해주었다.

 

마지막으로 중복값 제거를 위해서 Set을 사용했다.

 

코드

import java.util.*;

class Solution {
    String nums = "";
    Boolean[] visit = new Boolean[8];
    Set<Integer> s = new HashSet<>();

    public int solution(String numbers) {
        nums = numbers;
        Arrays.fill(visit, false);

        for(int i = 0; i < numbers.length(); i++) {
            if(nums.charAt(i) != '0') {
                visit[i] = true;
                bt(nums.charAt(i) + "");
                visit[i] = false;
            }
        }

        return s.size();
    }

    public void bt(String tmp){
        Integer x = Integer.parseInt(tmp);
        if(x != 0 && x != 1 && sosu(x)) s.add(x);

        for(int i = 0; i < nums.length(); i++) {
            if(visit[i]) continue;
            visit[i] = true;
            bt(tmp + nums.charAt(i) + "");
            visit[i] = false;
        }
    }

    public Boolean sosu(Integer x){
        for(int i = 2; i * i <= x; i++)
            if(x % i == 0) return false;

        return true;
    }

}