[프로그래머스] 소수 찾기 for JAVA _ 완전 탐색 알고리즘 + 순열, 소수찾기

 

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

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

 

 

 

 

문제

 

 

 

---

 

어려워

 

 

 

고려해야할점은

 

1. 숫자 조합하기

2. 소수인지 확인

 

 

 

소수인지 확인하는 방법은 에라토스테네스의 체를 사용함

 

 

숫자를 조합하는게 문제인데 누가봐도 순열임

 

 

순열이 뭐냐면 예를 들어 numbers = 0,1,2,3 이었다고 하면

 

나올 수 있는 수가

 

1자리수 : 0, 1, 2, 3

2자리수 : 01, 02, 03, 10, 12, 13, 20, 21, 23, 30, 31, 32

3자리수 : 012, 013, 021, 023, 031, 032, 102, 103, 120, 123, 어쩌구...

 

 

일케 나오는게 순열임

 

 

조합은 쟤네의 순서를 고려 안하는거라서 01 = 10 모두 하나로 치는 것이다.

 

 

 

암튼 이래서 순열을 만들어야하는데

 

 

다른사람꺼 참고했다.

 

 

 

코드

import java.util.*;
class Solution {
    HashSet<Integer> set = new HashSet<>(); // 순열로 만든 조합 넣음
    
    public int solution(String numbers) {
        int answer = 0;
        permutation("", numbers);
        
        Iterator<Integer> it = set.iterator(); // 요소 순차 처리
        while(it.hasNext()){
            int a = it.next(); // 하나씩 읽어와
            if(prime(a)) answer++;
        }
         
        
        return answer;
    }
    public void permutation(String prefix, String str){ // 순열
        int n = str.length();
        if(!prefix.equals("")){
            set.add(Integer.valueOf(prefix));
        }
        for(int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
    }
    
    public boolean prime(int 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 void permutation(String prefix, String str){ // 순열
        int n = str.length();
        if(!prefix.equals("")){
            set.add(Integer.valueOf(prefix));
        }
        for(int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
    }

 

 

 

 

여기가 중요하다!

 

 

DFS로 순열 만드는걸로 보인다.

 

 

 

저기 강조해놓은 부분이 어떻게 실행되는지 살펴보면

 

 

 

 

 

 

 

 

 

 

 

이렇게 진행된다.