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

문제 보기

n개의 값 중 n개를 뽑는 순열을 백트래킹으로 찾다 보면 모든 경우의 수가 나온다.

풀이

• 가능한 모든 수들을 찾아내기 위하여 백트래킹 사용
• "011" 의 경우 "101", "101" 등 같은 숫자가 나올 수 있기 때문에 checkedNumbers 사용
  
  
• numbers.length 개의 값 중에서 numbers.length 개의 숫자를 뽑는 순열을 찾는 것처럼 Backtracking 한다.
• checkedNumbers 에 있는 경우를 제외한 Backtracking 의 모든 과정에서 currNumber 가 소수인지 판별하여 소수가 맞으면 answer 을 1 증가 시킨다.
• answer 을 반환한다.

import java.util.ArrayList;
import java.util.List;

class Solution {

    static String numbers;
    static boolean[] visited;
    static List<Integer> checkedNumbers = new ArrayList<>();
    static int answer = 0;

    public int solution(String numbers) {
        this.numbers = numbers;
        visited = new boolean[numbers.length()];
        findPrimeNumber(0);

        return answer;
    }

    public void findPrimeNumber(int currNumber) {
        if (checkedNumbers.contains(currNumber)) {
            return;
        }

        checkedNumbers.add(currNumber);
        if (isPrimeNumber(currNumber)) {
            answer++;
        }

        for (int i = 0; i < numbers.length(); i++) {
            if (visited[i]) {
                continue;
            }

            visited[i] = true;
            int nexNumber = Integer.parseInt(String.valueOf(currNumber) + numbers.charAt(i));
            findPrimeNumber(nexNumber);
            visited[i] = false;
        }
    }

    public 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;
    }
}