[프로그래머스] 소수 찾기 - 완전탐색(lv2)

programmers.co.kr/learn/courses/30/lessons/42839?language=java

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

import java.util.*;
class Solution {
	int answer = 0;
	HashSet<Integer> hs = new HashSet<Integer>();
    
	public int solution(String numbers) {
    	char arr[] = numbers.toCharArray();
    	char output[] = new char[numbers.length()];
    	boolean select[] = new boolean[arr.length];
    	permutation(arr, output, select, 0);
        return this.answer;
    }
    
	private void permutation(char[] arr, char[] output, boolean[] select, int cnt) {
		if(cnt >= 1) {
			if(isPrime(output, cnt)) {
				this.answer++;
			}
		}
		
		for(int i=0; i<arr.length; i++) {
			if(select[i] == true) continue;
			select[i] = true;
			output[cnt] = arr[i]; 
			permutation(arr, output, select, cnt+1);
			select[i] = false;
		}
	}
	
	private boolean isPrime(char[] output, int cnt) {
		if(output[0] == '0') return false;
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<cnt; i++) {
			sb.append(output[i]);
		}
		int temp = Integer.parseInt(sb.toString());
		if(hs.contains(temp) || temp == 1) return false;
		hs.add(temp);
		
		for(int i=2; i*i<=temp; i++) {
			if(temp%i == 0) return false;
		}
		return true;
	}
}

소요시간 : 30분

문자열을 toCharArray를 이용해서 char배열에 옮겨담아서 permutation함수를 통해 완전탐색을 합니다.

cnt의 값은 자릿수를 나타내며, 1일때 1자리, 2일때 2자릿수의 값을 확인합니다.

isPrime함수에서는 011, 11과 같은 중복을 방지하기위해 첫자리가 0일 경우 false를 반환했고,

HashSet을 이용해서 같은 값에 대한 중복처리를 했습니다.

소수 체크는 일반적인 방법으로 특정 값에 대하여 i = 2부터 i <= sqrt(temp)까지 i을 나눠보면서 나머지가 0이 있으면 false를 반환하도록 했습니다.