[프로그래머스 JAVA] 42839. 소수 찾기

문제 링크

---

 

프로그래머스

 

접근 방법

---

1. 만들 수 있는 모든 수를 순열로 구해줍니다.
2. 같은 숫자인 경우를 처리해야 하므로 set을 사용합니다.
3. 최대 7자리 수이기 때문에 에라토스테네스의 체를 사용합니다.

소스 코드

---

import java.util.*;

class Solution {
    char[] ch, bf = new char[7];
    List<Integer> arr = new LinkedList<>();
    boolean[] visited;

    void permutation(int idx, int num) {
        if (idx == num) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < idx; i++) {
                sb.append(bf[i]);
            }
            arr.add(Integer.valueOf(sb.toString()));

            return ;
        }

        for (int i = 0; i < ch.length; i++) {
            if (visited[i]) {
                continue;
            }
            bf[idx] = ch[i];
            visited[i] = true;
            permutation(idx + 1, num);
            visited[i] = false;
        }
    }
    
    public int solution(String numbers) {
        ch = numbers.toCharArray();
        visited = new boolean[ch.length];

        for (int i = 1; i <= ch.length; i++) {
            permutation(0, i);
        }

        Set<Integer> set = new HashSet<>(arr);
        boolean[] prime = new boolean[Integer.parseInt(new String("1").repeat(ch.length)) * 9 + 1];
        
        prime[0] = prime[1] = true;
        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            if (prime[i]) {
                continue;
            }

            for (int j = i + i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }

        int cnt = 0;
        for (int i : set) {
            if (!prime[i]) {
                ++cnt;
            }
        }
        
        return cnt;
    }
}

코드 설명

---

순열을 이용하여 1자리 수부터 num까지의 만들 수 있는 모든 수를 구해줍니다.

구한 수에서 중복이 있을 수 있으므로 set을 사용하여 중복을 제거합니다.

에라토스테네스의 체를 이용하여 소수들을 구한 다음, set에 있는 소수들이 몇 개인지 세어줍니다.