프로그래머스 소수 찾기 JAVA

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

문제

해당 문제는 문자열로 숫자가 주어졌을 때 해당 숫자를 조합해 만들 수 있는 숫자 중 소수의 개수를 찾는 문제다.

조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
• 11과 011은 같은 숫자로 취급합니다.

풀이

해당 문제는 Set을 이용해서 중복 숫자를 관리했고, 문자를 조합하기 위해 중복순열을 이용해 변환하여 사용하였다. 소수를 판단하기 위해서 구글링을 진행하였고 알고자 하는 숫자의 제곱근까지 체크하는 방법을 알게 되어 해당 방법으로 진행했다. 쉽게 말하면 제곱근까지 체크하면 해당 숫자의 약수들의 중간값까지는 모두 체크가 되므로 가장 효율적으로 소수를 판단 가능하다.

코드

import java.util.HashSet;
import java.util.Set;

class Solution {
   static String out = ""; // 숫자 만든거 저장
	static boolean[] select; 
	static Set<Integer> set = new HashSet<>();
	public static int solution(String numbers) {
		int answer = 0;
		select = new boolean[numbers.length()];
		for (int i = 0; i < select.length; i++) { // 1부터 원하는 길이만큼 숫자를 만듬
			perm(0,numbers,i+1);
		}
		for (Integer n : set) { // 소수 체크하는 부분
			if(check(n))
				answer++;
		}
		return answer;
	}

	private static boolean check(Integer n) {
		if(n == 0 || n == 1) // 0이나 1은 소수가 아니니깐 실패
			return false;
		for (int i = 2; i <= Math.sqrt(n); i++) { // 나머지 애들은 제곱근까지만 반복하면서 나눠줌 (소수 찾기 방법
			if(n%i == 0)
				return false;
		}
		return true;
	}

	private static void perm(int index, String str, int len) {
		if(index == len) { // 원하는 길이가 될때마다 set에 저장
			set.add(Integer.parseInt(out));
			return;
		}
			
		for (int i = 0; i < select.length; i++) {
			if (select[i]) // 이미 해당숫자 사용했으면
				continue;
			out += str.charAt(i); //해당 숫자를 추가시켜줌
			select[i] = true;
			perm(index + 1,str,len);
			select[i] = false;
			out = out.substring(0,out.length()-1); // 마지막에 추가한 숫자를 뺴준다.
		}
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드