[프로그래머스] level2 42839 - 소수 찾기(Java)

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

접근 방법

순열로 모든 경우의 수를 구한다.

public int solution(String numbers) {
        // 길이가 1부터 n까지의 모든 순열 탐색
        for(int i=1;i<=numbers.length();i++){
            permutation(numbers.split(""), 0, numbers.length(), i);
        }

        return answer;
    }

    public void permutation(String[] arr, int depth, int n, int r){
        	// r개의 데이터를 뽑았을 때 코드 적기
            return;
        }

        for(int i=depth;i<n;i++){
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }

순열 코드는 외워두자.

소스 코드

package programmers.level2.pm42839;

import java.util.*;

public class Solution {

    static int answer = 0;
    static Set<Integer> set = new HashSet<>();

    public int solution(String numbers) {
        for(int i=1;i<=numbers.length();i++){
            permutation(numbers.split(""), 0, numbers.length(), i);
        }

        return answer;
    }

    public void permutation(String[] arr, int depth, int n, int r){
        if(depth == r){
            String temp = "";
            for(int i=0;i<r;i++){
                temp += arr[i];
            }
            if(isPrime(Integer.parseInt(temp))){
                set.add(Integer.parseInt(temp));
                answer++;
            }
            return;
        }

        for(int i=depth;i<n;i++){
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }

    public void swap(String[] arr, int depth, int i){
        String temp = arr[i];
        arr[i] = arr[depth];
        arr[depth] = temp;
    }

    public boolean isPrime(int num){
        if(set.contains(num)){
            return false;
        }

        if(num < 2){
            return false;
        }

        for(int i=2;i*i<=num;i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }
}