99 클럽 코테 스터티 15일차 TIL + 프로그래머스 소수 찾기 java

1. 문제 설명

문제 설명

2. 접근 방식

KEY WORD: 브루트 포스

(1) 문자열로 받은 숫자를 한 자릿수가 되게 나누어서 배열에 저장한다.

(2) 전체 숫자가 n개라면 그 중 k개를 뽑아서 나열한다. (순열, k = 1 ~ n )

(3) 나열된 k개의 수를 합쳐서 하나의 숫자로 만들고, 소수 판별한다. (소수 판별법 이용)

(4) 소수 판별이 확정되면 해당 수가 이전에 나왔는지, hashSet으로 체크한다. 없으면, 소수의 개수를 +1 올린다.

 

 

※추신※

(1)
나는 한자리 수를 합치는 것을 원래의 수 * 10 + 새로 들어온 한 자리 수로 그때 그때 바로 했다.

(2)
소수 판별법을 모른다면, 정리 잘 한 사람 링크를 보고 오기 바란다. 해당 링크에서는 왜 n의 제곱근까지만 나눠서 확인하면 되는지 나와있다.

(3)
소수 판별하려는 값이 1인 경우 1은 소수가 아니므로 예외 처리가 필요하다.
제일 큰 자리수가 0이면 안되므로 ex- 011 그에 대한 예외 처리도 해준다.

3. 코드 분석

import java.io.*;
import java.util.*;

class Solution {

    static int cnt = 0;
    static HashSet<Integer> values = new HashSet<>();

    public int solution(String numbers) {
        int [] num = new int [numbers.length()];
        for(int i = 0; i < numbers.length(); i++){
            num[i] = numbers.charAt(i) - 48;
        }
        Arrays.sort(num);
        for(int i = 1; i <= num.length; i ++) {
            permutation(num, new boolean [num.length], 0, i, 0);
        }

        return cnt;
    }

    public void permutation(int [] num, boolean [] isVisited, int depth, int end, int now) {           
        // 기저 조건
        if(depth == end){

            if(now == 1) return;

            if(isPrime(now) && !values.contains(now)) {
                values.add(now);
                cnt++;
            }
            return;
        }
        // 계산식 
        for(int i = 0; i < num.length; i++){

            if(depth == 0 && num[i] == 0) continue;

            if(!isVisited[i]){
                isVisited[i] = true; 
                now = now*10 + num[i];
                permutation(num, isVisited, depth+1, end, now);
                now = now/10;
                isVisited[i] = false; 
            }
        }
    }
    // 소수 판별
    public boolean isPrime(int v) {
        for(int i = 2; i <= Math.sqrt(v); i ++){
            if(v%i == 0) return false;
        }
        return true;
    }
}