[완전탐색] 소수찾기 - Java 풀이, 순열 포인트,★★

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

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

 

문제

 

접근법

이것은 순열이 필요해 보인다. 모든 경우에 수로 순열로 만들고,

중복을 제거 해야 한다. (HashSet에 담으면 해결될것 같음)

중복 제거된 리스트에서 소수를 찾아서 count 해주면 끝!

 

포인트

1. 순열을 만드는 메소드의 구현 (그동안 순열 조합 코드를 안해봐서 이번기회에 외울 예정)

2. 소수검사는 아리토스텔레스의 채에 따라 제곱근 값까지만, 나누어떨어지는 값이 있는지 검사해주면 된다.

 

 

풀이

public static void permutation(String prefix, String str, HashSet<Integer> set) { 
  int n = str.length();        
  if(!prefix.equals("")) {
    set.add(Integer.valueOf(prefix)); //스트링을 Interger로 변환
  }       
  // 문자열이 공백이 들어오면 더이상 재귀호출 하지 못함
  for (int i = 0; i < n; i++){
    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
  }

}  

// 소수 판별 메소드
public static boolean isPrime(Integer a) {
  if(a==0 || a==1) {
    return false;
  }
  else {
    for(int i=2;i<=Math.sqrt(a);i++)
      if(a%i==0)   return false;
  }
  return true;
}

public static int solution(String numbers) {
  HashSet<Integer> set = new HashSet<Integer>();  
  permutation("", numbers, set); //순열
   
  Iterator<Integer> it = set.iterator();
  int count=0;
  while(it.hasNext()) {
    int a = it.next();
    if(isPrime(a))
      count++;
  }    
  return count;
}

 

순열을 만드는 부분과 소수검사부분 모두 참조했지만,

꼭 기억해두자.

 

소수검사시에는 추가로 2를 제외한 짝수는 소수가 될수 없으므로 검사시

i = 3 ~ 홀수단위로 검사해주는것도 효율성을 좀더 올리는 방법이다!

// 소수 판별 메소드
public static boolean isPrime(Integer a) {
  if(a==0 || a==1) {	// 0, 1은 소수가 아니므로 제외
    return false;
  }
  else if(a==2)		// 2는 따로 처리하고
  	return true;
  else {
    for(int i=3;i<=Math.sqrt(a);i+=2)	// 요렇게 홀수만 검사하면 효율성 UP
      if(a%i==0)   return false;
  }
  return true;
}

 

순열 생성부분도 놀라운 코드가 아닐수 없다. 누구신지 천재같다.

public static void permutation(String prefix, String str, HashSet<Integer> set) { 
  int n = str.length();        
  if(!prefix.equals("")) {
    set.add(Integer.valueOf(prefix)); //스트링을 Interger로 변환
  }        
  for (int i = 0; i < n; i++){
    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
  }

permutation (prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

이부분에서 String의 범위를 자기자신을 제외한 문자열로 반환해주는 부분

str.substring(0, i) + str.substring(i+1, n)

어메이징 뷰티풀 판타스틱 섹시 코드다!