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

문제

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

프로그래머스

---

접근 방식

numbers의 길이가 최대 7이기 때문에 만들 수 있는 모든 경우의 수를 다 해도 아주 크지 않다.

길이개수

1	7
2	7 x 6
3	7 x 6 x 5
...	...
7	7 x 6 x 5 x ... x 2 x 1

따라서 완전 탐색으로 모든 경우의 수를 구하고 그 중 소수인 수를 찾으면 된다.

---

풀이

문자열 입력을 숫자형 배열로 바꾸기

입력이 문자열(numbers)로 주어지기 때문에 이를 한 글자씩 숫자로 바꿔서 배열(numberArr)에 저장한다.

int[] numberArr = new int[numbers.length()];
for(int i=0; i<numbers.length(); i++){
    numberArr[i] = numbers.charAt(i) - '0';
}

재귀함수로 모든 경우의 수 구하기

위에서 구한 numberArr 의 숫자들로 만들 수 있는 모든 숫자를 재귀함수를 통해서 구한다.
중복을 제거하기 위해 Set에 숫자들을 저장했다. 또 각 숫자는 한번씩만 사용이 가능하기 때문에 방문처리를 위해 배열을 하나 만들어줬다.

Set에 값을 넣을 때 Integer형으로 넣어주는데 입력 값이 빈 값이면 숫자로 변환할 수 없기 때문에 값이 빈 값일 때는 넘어가도록 했다.
재귀함수의 종료 조건은 깊이가 numberArr의 길이와 같을 때, 즉 numberArr의 숫자를 모두 사용했을 때로 했다.

재귀호출을 할 때에는 depth를 +1 하고, num에 현재 숫자를 하나 붙여준다.

이 함수를 다 돌고 나면 Set에는 numberArr의 숫자들로 만들 수 있는 모든 경우의 수가 들어있게 된다.

void findNum(int[] arr, boolean[] visited, int depth, String num){
    if(!num.equals(""))
        numsSet.add(Integer.parseInt(num));
        
    if(depth == arr.length){
        return;
    }
        
    for(int i=0; i<arr.length; i++){
        if(!visited[i]){
            visited[i] = true;
            findNum(arr, visited, depth + 1, num + arr[i]);
            visited[i] = false;
        }
    }
}

소수 찾기

주어진 수가 소수인지 아닌지를 판별하는 함수를 따로 만들었다. 소수를 찾는 알고리즘에는 여러 가지가 있지만 여기에서는 Math.sqrt를 사용해서 구했다.

0과 1은 소수가 아니므로 제외하고, 그 외에 숫자들을 소수인지 판별한다.
2부터 자기자신의 제곱근까지의 숫자로 나눴을 때 나눠 떨어지지 않는다면 소수이고, 하나라도 나눠 떨어지는 숫자가 있다면 소수가 아니다.

소수라면 true를, 소수가 아니라면 false를 return 한다.

---

전체 코드

import java.util.*;

class Solution {
    
    Set<Integer> numsSet = new HashSet<>();
    
    public int solution(String numbers) {
        int answer = 0;
        
        int[] numberArr = new int[numbers.length()];
        for(int i=0; i<numbers.length(); i++){
            numberArr[i] = numbers.charAt(i) - '0';
        }
        
        // 방문 처리를 위한 배열
        boolean[] visited = new boolean[numberArr.length];
        findNum(numberArr, visited, 0, "");
        
        // Set에서 소수의 개수 count 하기
        for(int i : numsSet){
            if(isPrime(i)) {
                answer ++;
            }
        }
        
        return answer;
    }
    
    void findNum(int[] arr, boolean[] visited, int depth, String num){
        if(!num.equals(""))
            numsSet.add(Integer.parseInt(num));
        
        if(depth == arr.length){
            return;
        }
        
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                findNum(arr, visited, depth + 1, num + arr[i]);
                visited[i] = false;
            }
        }
    }
    
    boolean isPrime(int num){
        if(num < 2) return false;
        
        for(int i=2; i<=Math.sqrt(num); i++){
            if(num % i == 0){
                return false;
            }
        }
        
        return true;
    }
}