[프로그래머스] 소수찾기 -Java

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

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

import java.util.HashSet;
import java.util.Set;
class Solution {
	    public int solution(String numbers) {
	        
	        int len=numbers.length();
	        Set <Integer> set =new HashSet<>(); //중복체크
	        boolean [] check= new boolean[len]; //방문체크
	        int [] num= new int[len]; //방문체크
	        for(int i=1; i<=len; i++) {
	        	permutation(0,i,numbers,set,check, num);
	        }
	        return set.size();
	    }

		private void permutation(int cnt, int end, String numbers, Set<Integer> set, boolean[] check, int[] num) {
			if(cnt==end) {
				String make="";
				for(int i=0; i<end; i++) {
					make+=num[i];
				}
				
				int primeCheckNum=Integer.parseInt(make);
				if(set.contains(primeCheckNum) || primeCheckNum==0 || primeCheckNum == 1) return; //중복이라면 넘어가 
				if(primeCheckNum==2) {
					set.add(primeCheckNum); 
					return;
				}
				
				for(int i=2; i*i<=primeCheckNum; i++) {
					if(primeCheckNum%i==0) return;
				}
				set.add(primeCheckNum);
				return ;
			}
			for(int i=0; i<numbers.length(); i++) {
				if(check[i]) continue;
				check[i]=true;
				num[cnt]=numbers.charAt(i)-'0';
				permutation(cnt+1, end, numbers, set, check, num);
				check[i]=false;
			}
		}
	}

 

소요시간 : 20분

 

오랜만에 알고리즘을 푸니까 순열 짜는 게 생각이 안 나서 좀 걸렸습니다.

문제 자체는 순열만 짜면 쉽게 풀립니다!

 

숫자의 중복을 체크해주기 위해 Set을 사용했습니다.

 

우선 1~숫자의 길이만큼 순열을 돌려줍니다.

그리고 순열이 하나씩 만들어지면 맨앞의 숫자 0을 없애주기 위해 String으로 바꿨다가 다시 int로 바꿔줍니다!

 

그 후에 소수를 판별해줍니다. 소수를 판별할 때는 

i=2부터 i*i<=소수판별할 숫자까지 돌리면서 소수를 판별합니다.

 

예를 들어 숫자가 18이라면 18의 약수는 (1,18), (2,9), (3,6) 이런 식으로 나오게 됩니다.

루트 18 -> 4.xxxx가 넘어가게 되면 나누어지는 수가 없다고 판단할 수 있습니다.

 

 

이런 식으로 숫자의 중복을 피해서 소수를 판별하면 됩니다! 끝!