[프로그래머스/완전탐색] Level 2 소수 찾기 (JAVA)

문제

---

1차 풀이 (2021.02.24)

순열 알고리즘을 다시 한 번 적용할 수 있는 문제였다.

1. 주어진 numbers에서 각 자리 숫자들을 추출해서 digits에 저장한다.
2. makePrimeNumbers()에서 digits를 이용해 순열을 만든 후 소수인 경우 primeNumbers에 저장한다.
   • 순열은 DFS로 구현했다.
   • 소수 체크는 제곱근까지 수로 나눴을 때의 나머지를 체크하도록 구현했다.

코드

import java.util.*;

class Solution {
    
    private static final int ASCII_BASE = 48;

    private List<Integer> digits = new ArrayList<>();
    private Set<Integer> primeNumbers = new HashSet<>();

    public int solution(String numbers) {
        extractDigits(numbers);
        makePrimeNumbers();
        return primeNumbers.size();
    }

    private void extractDigits(String numbers) {
        for (char number : numbers.toCharArray()) digits.add(number - ASCII_BASE);
    }

    private void makePrimeNumbers() {
        boolean[] visited = new boolean[digits.size()];
        int[] result = new int[digits.size()];
        dfs(visited, result, 0);
    }

    private void dfs(boolean[] visited, int[] result, int depth) {
        int number = makeNumber(result);
        if (isPrimeNumber(number)) primeNumbers.add(number);

        for (int i = 0; i < digits.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = digits.get(i);
                dfs(visited, result, depth + 1);
                visited[i] = false;
                result[depth] = 0;
            }
        }
    }

    private int makeNumber(int[] result) {
        int number = 0, unit = 1;
        for (int digit : result) {
            number += digit * unit;
            unit *= 10;
        }
        return number;
    }

    private boolean isPrimeNumber(int number) {
        if (number < 2) return false;
        for (int i = 2; i <= Math.sqrt(number); i++)
            if (number % i == 0) return false;
        return true;
    }
}

---

2차 풀이 (2021.08.27)

브루트포스로 쉽게 풀 수 있는 문제였다.

다만 중복 체크하는 걸 깜빡해서 한 번 틀렸고,
count만 증가하는 방식에서 Set에 완성된 소수들을 저장하는 방식으로 수정했다.

위에 코드를 보니 쓸데없는 부분이 많은 것 같다.. 지금 내 맘에 드는 건 아래 코드,,,

코드

import java.util.*;

class Solution {
    
    private Set<Integer> primeNumbers = new HashSet<>();
    
    public int solution(String numbers) {
        char[] digits = numbers.toCharArray();
        
        for (int i=0 ; i<digits.length ; i++) {
            if (digits[i] == '0') {
                continue;
            }
            
            boolean[] visited = new boolean[digits.length];
            visited[i] = true;
            
            permutation(""+digits[i], digits, visited);
        }
        
        return primeNumbers.size();
    }
    
    private void permutation(String current, char[] digits, boolean[] visited) {        
        int number = Integer.parseInt(current) ;
        
        if (isPrime(number)) {
            primeNumbers.add(number);
        }
        
        for (int i=0 ; i<digits.length ; i++) {
            if (!visited[i]) {
                visited[i] = true;
                permutation(current+digits[i], digits, visited);
                visited[i] = false;
            }
        }
    }
    
    private boolean isPrime(int number) {
        if (number < 2) {
            return false;
        }
        
        for (int i=2 ; i<=Math.sqrt(number) ; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}