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

문제를 크게 두 부분으로 나눌 수 있다.

 

1. 낱말카드로 생성가능한 모든 수 만들기

2. 소수 검사

 

1번이 되게 애를 먹여서.. 결국 다른 사람의 코드를 참고했다. (참고 : https://hoho325.tistory.com/201)

핵심은 바로 순열을 이용하는 것이다.

 

순열과 set 자료구조를 이용하여 중복없는 숫자들을 생성하고 소수인지 검사하여 개수를 세어주면 된다.

 

package Programmers;

import java.util.*;

public class bruteforce2 {
	static char[] chs;
    static boolean[] visited; //순열 탐색할때 사용
    static HashSet<Integer> set;
    static char[] select;
    
	static int solution(String numbers) {
        chs=numbers.toCharArray();
        visited=new boolean[numbers.length()]; //순열 탐색할때 사용
        
        set=new HashSet<Integer>();	//순열 저장용 set, 중복 없이 저장
        
        //1Pr,2Pr ... rPr 찾기
        for(int i=1;i<=numbers.length();i++) {
        	select=new char[i];				// 선택된 char을 담는 변수
        	perm(0,i,numbers.length());		//nPr 찾기
        }
        
        int answer=set.size();
        return answer;
    }
	static void perm(int start,int r,int n) {
		//끝까지 모두 찾은 경우 -> 숫자로 변환하여 소수인지 검사하고 저장하기
		if(start==r) {
			//1 선택된 select변수를 숫자로 변환
			String str="";
			for(int i=0;i<select.length;i++) str+=select[i];
			int num=Integer.parseInt(str);
			
			if(num==1 || num==0) return; // 1과 0은 소수가 아님
			
			//2 소수 검사
			boolean flag=false;
			// num의 제곱근까지 나누어 보며 나눠지는 숫자 있는지 확인
			for(int i=2;i<=Math.sqrt(num);i++) {
				if(num%i==0) flag=true;
			}
			
			//3 저장
			if(!flag) set.add(num);
			return;
		}
		
		for(int i=0;i<n;i++) {
			if(!visited[i]) {
				visited[i]=true;
				select[start]=chs[i];
				perm(start+1,r,n);
				visited[i]=false;
			}
		}
	}
	
	public static void main(String[] args) {
		String numbers="17";
		int answer=solution(numbers);
		System.out.println(answer);
	}

}

 

순열(Permutaion) 알고리즘

1.순열을 담을 배열을 static으로 select 배열을 선언한다
2. visited 배열을 N 크기로 선언한다(boolean)perm 함수를 작성한다
3. perm(int start, int r, int n)start를 0부터 증가시키면서 select 배열에 순차적으로 넣습니다.
4. visited도 방문처리 해줍니다.재귀적으로 perm(start+1, r, n)을 호출합니다.
5. start가 r이 될 때까지 즉 r개의 수를 뽑아 순열을 만듭니다

 

순열 알고리즘은 이 방법과 같이 visited를 이용할 수 있다.

또 다른 방법은 swap을 이용하는 것이다.

 

swap을 이용하여 문제를 해결한 블로그 글이다. (https://beaniejoy.tistory.com/38)