[programmers] 소수 찾기

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

import java.util.Set;
import java.util.HashSet;

class Solution {
    Set<Integer> answer = new HashSet<>();
    public int solution(String numbers) {
        boolean[] picked = new boolean[numbers.length()];
        for(int i=1; i<=numbers.length(); i++) {
            backtrack(numbers, "", i, picked);
        }
        return answer.size();
    }
    private void backtrack(String numbers, String letter, int maxLen, boolean[] picked) {
        //종료 조건
        if(maxLen == letter.length()) {
            if(isPrime(Integer.parseInt(letter))) {
                answer.add(Integer.parseInt(letter));
            }
            return;
        }
        //process
        for(int i=0; i<numbers.length(); i++) {
            if(!picked[i]) {
                picked[i] = true;
                letter += numbers.charAt(i);
                backtrack(numbers, letter, maxLen, picked);
                letter = letter.substring(0, letter.length()-1);
                picked[i] = false;
            }
        }
    }

    private boolean isPrime(int num) {
        if(num == 0 || num == 1) return false;
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}