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

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

프로그래머스

 

 

Review

순열 + DFS 의 문제였다. 우선, 주어진 숫자들로 만들 수 있는 모든 수를 구하기 위해 순열을, 중복되지 않는 소수만 저장할 수 있도록 Set을 사용했다. 각 자리에 숫자를 하나씩 추가하면서, 그 숫자가 사용되었는지 visited 배열을 통해 확인하고, 사용된 숫자는 다시 선택되지 않도록 했다. 수가 조합될 때마다 문자열로 만들어 소수 판별을 해주었다. 이때, 평소에 사용하던 소수판별법이 아니라, 에라토스테네스의 체 개념을 사용해보았다. (참고: 에라토스테네스의 체)

개인적으로 함수에 매개변수를 많이 사용하는 걸 어려워하는데, 이번 문제 역시 그랬다. 적재적소에 사용할 수 있도록 정진... 필요...ㅠ

 

 

Code

import java.util.*;

class Solution {
    public int solution(String numbers) {
        Set<Integer> primes = new HashSet<>();
        char[] numArray = numbers.toCharArray();
        
        for (int i = 1; i <= numArray.length; i++) {
            permutation(numArray, new boolean[numArray.length], "", primes, i);
        }
        return primes.size();
    }
    
    private void permutation(char[] numArray, boolean[] visited, String current, Set<Integer> primes, int length) {
        if (current.length() == length) {
            int num = Integer.parseInt(current);
            
            if (isPrime(num)) {
                primes.add(num);
            }
        }
        
        for (int i = 0; i < numArray.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            permutation(numArray, visited, current + numArray[i], primes, length);
            visited[i] = false;
        }
    }
    
    private boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        
        // 에라토스테네스의 체
        for (int i = 2; i <= Math.sqrt(num); i++) {	
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}