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

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

프로그래머스

이 문제는 문자열이 들어오고 그 문자열을 가지고 만들 수 있는 소수의 수를 찾는 것이다.

예를 들어 "17" 이 들어오면 만들 수 있는 수는 1, 7, 17, 71이 되고 소수는 7, 17, 71이므로 3개이다.

 

핵심

우선 완전탐색(bfs)을 사용하여 가능한 모든 경우를 찾는다.

이후 소수를 판별해야 하는데 에라스토테네스의 체를 사용하면 된다.

에라스토테네스의 체를 예전에도 설명한 적이 있는데, 간단하게 설명하자면

소수를 구하려고 하는 값에 루트를 씌운 값까지만 찾으면 된다.

 

정답 코드

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

class Solution {
    char[] paper;
    boolean[] visited;
    Set<Integer> set = new HashSet<>();
    public int solution(String numbers) {
        paper = new char[numbers.length()];
        visited = new boolean[numbers.length()];
        for (int i = 0; i < numbers.length(); i++) {
            paper[i] = numbers.charAt(i);
        }
        dfs("", 0);
        return set.size();
    }

    public void dfs(String value, int index){
        if (!value.equals("")){
            int number = Integer.parseInt(value);
            if (isPrime(number)) set.add(number);
        }
        if (paper.length == index)return;
        for (int i =0; i< paper.length; i++){
            if (!visited[i]){
                visited[i] = true;
                bfs(value+paper[i],index+1);
                visited[i] = false;
            }
        }
    }

    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;
    }
}

해설

앞서 말한 대로 dfs를 통해 가능한 수를 찾고, 그 수가 소수인지 판별한다.

만약 소수라면 set에 넣게 된다. set을 사용한 이유는 중복을 제거하기 위함이다.

ex) 011 , 11 

위의 순서대로 간단하게 풀 수 있다.