[프로그래머스] Lv.2 : 소수 찾기 - 자바[Java]

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

프로그래머스

풀이

1. 에라토스테네스의 체를 사용하여 소수를 구한다. notPrime[i] = false라면 i는 소수이다.

2. char[] words에 한 글자씩 순서대로 숫자를 저장한다.

3. 길이가 1 ~ words.length인 순열을 구해서 숫자를 만들고, 그 숫자가 소수인지 판별하여 개수를 카운트한다.

코드

class Solution {
    static boolean[] notPrime = new boolean[10000000]; // false라면 소수
    static boolean[] check = new boolean[10000000]; // 순열을 통해서 이미 만든 숫자라면 true
    static boolean[] visited; // 순열을 만들 때 숫자가 중복 사용되지 않도록 판별하는 배열
    static int[] pm; // 순열 순서 저장
    static char[] words;
    static int cnt = 0;
    
    public int solution(String numbers) {
        // 소수 구하기
        notPrime[0] = true;
        notPrime[1] = true;
        for (int i = 2; i * i < 10000000; i++) {
            if (notPrime[i]) continue;
            for (int j = i * i; j < 10000000; j+= i) {
                notPrime[j] = true;
            }
        }
        
        // words에 numbers 저장
        words = new char[numbers.length()];
        for (int i = 0; i < words.length; i++) {
            words[i] = numbers.charAt(i);
        }
        
        // 길이가 1 ~ words.length인 순열로 만들 수 있는 숫자 구하기
        for (int i = 1; i <= words.length; i++) {
            visited = new boolean[words.length];
            pm = new int[i];
            permutation(0, i);
        }
        
        return cnt;
    }
    
    static void permutation(int len, int size) {
        if (len == size) {
            String str = "";
            for (int i = 0; i < len; i++) {
                str += words[pm[i]];
            }
            
            int num = Integer.parseInt(str);
            if (!check[num] && !notPrime[num]) { // 이미 만들어본 숫자가 아니면서 소수인 경우 카운트
                check[num] = true;
                cnt++;
            }
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (visited[i]) continue;
            
            visited[i] = true;
            pm[len] = i;
            permutation(len+1, size);
            visited[i] = false;
        }
    }
}

 

다른 풀이

- boolean[] check를 만들지 않고 HashSet을 사용하여 중복 숫자 제거

- boolean[] notPrime을 만들지 않고 따로 함수로 만들어 소수 여부를 판별

 

로직

- HashSet 생성 후 순열 시작

- 만들 수 있는 모든 문자열에 대해 Set에 추가

- Set을 순회하면서 숫자가 소수라면 카운트

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

        public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}

이전 풀이는 같은 순열 과정을 여러번 반복하지만, 이 풀이는 반복하지 않으므로 시간이 더 적게 걸린다.