소수찾기 - 프로그래머스 (Java, Level 2)

처음 풀이

dfs로 숫자들을 배열한다.

숫자 배열하는 중간중간 소수인지 확인하고 소수면 Set에 저장한다.

최종적으로 Set의 size를 리턴한다.

 

1. solution()

전역 변수들 초기화

 

Set<Integer> primeSet;
String[] numStrArr;
boolean[] isUsed;
StringBuilder sb;

public int solution(String numbers) {
    int totalLength = numbers.length();
    primeSet = new HashSet<>();
    numStrArr = new String[totalLength];
    isUsed = new boolean[totalLength];
    sb = new StringBuilder();

    for (int i = 0; i < totalLength; i++) {
        numStrArr[i] = numbers.substring(i, i+1);
    }//for end

    dfs(0, totalLength);

    return primeSet.size();
}//solution() end

 

2. 소수 판별 method

2부터 본인의 제곱근까지 나눠 떨어지는지 확인하면 된다.

 

public boolean isPrime(int n) {
    if (n==0 || n==1) return false;

    for (int i = 2; i <= (int)(Math.sqrt(n)); i++) {
        if (n%i == 0) return false;
    }//for end

    return true;
}//isPrime() end

 

3. DFS 탐색

숫자 배치하는 중간마다 소수인지 확인하기 때문에 모든 길이에 대해 처리 가능하다.

재귀 중단 조건은 문자열 길이가 전체 길이와 같아지는 것이다.

 

public void dfs(int length, int totalLength) {
    //소수인지 확인, 소수면 set에 저장
    if (sb.length()>0 && isPrime(Integer.parseInt(sb.toString()))) {
        primeSet.add(Integer.parseInt(sb.toString()));
    }
    //중단 조건
    if (length==totalLength) return;

    for (int i = 0; i < numStrArr.length; i++) {
        if (!isUsed[i]) {
            isUsed[i] = true;
            sb.append(numStrArr[i]);
            dfs(length+1, totalLength);
            isUsed[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }//for end
}//dfs() end