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

문제 : 소수찾기 - Programmers

풀이과정

1. Permutation을 이용하여 주어진 숫자 카드들로 만들 수 있는 모든 경우의 수를 구한다. 참고
2. 모든 경우의 수를 계산할 때, 카드를 1장만 사용해서 만드는 경우의 수 부터(맨 앞에서 1자리만) 카드를 n장 사용해서 만드는 경우의 수(맨 앞에서부터 n장)까지 모든 수를 Set에 저장한다. (1 ≤ n ≤ 전체 카드의 수)
3. 2의 결과로부터 Set에는 주어진 카드들로 만들 수 있는 모든 정수가 적혀 있다. 여기서 가장 큰 값을 계산한다. → Collections.max()
4. 3의 결과로 얻은 수에 대해서 에라토스테네스의 체 알고리즘을 사용하여 1부터 해당 수 까지의 소수 테이블을 구한다.
5. 4의 결과로 얻은 테이블을 사용하여 Set에 들어있는 모든 숫자들이 소수인지 판별한다.

소스코드

package bruteforce;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class FindPrimeNumber {
    public int solution(String numbers) {
        char[] nums = numbers.toCharArray();
        // 1장을 사용해서 만들 수 있는 숫자부터 n 장을 사용해서 만들 수 있는 숫자까지 모두 고려
        Set<Integer> createdNums = new HashSet<Integer>();
        for(int i = 1; i <= nums.length; i++) {
            permutation(nums, 0, i, createdNums);
        }

        boolean[] primeTable = getPrimeNumberTable(Collections.max(createdNums));

        int count = 0;
        for (Integer createdNum : createdNums) {
            if (primeTable[createdNum]) {
                count++;
            }
        }

        return count;
    }

    private void permutation(char[] chars, int depth, int r, Set<Integer> resultContainer) {
        if (depth == r) {
            StringBuilder answer = new StringBuilder();
            for (int i = 0; i < r; i++) {
                answer.append(chars[i]);
            }
            resultContainer.add(Integer.valueOf(answer.toString()));
            return;
        }

        for (int i = depth; i < chars.length; i++) {
            this.swap(chars, i, depth);
            this.permutation(chars, depth + 1, r, resultContainer);
            this.swap(chars, i, depth);
        }
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    private boolean[] getPrimeNumberTable(int upperBound) {
        boolean[] primes = new boolean[upperBound + 1];
        Arrays.fill(primes, true);

        primes[0] = false;
        primes[1] = false;

        for (int i = 2; i * i <= upperBound; i++) {
            if (primes[i]) {
                for (int j = i * 2; j <= upperBound; j += i) {
                    primes[j] = false;
                }
            }
        }

        return primes;
    }
}