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

🔗문제로 이동 👉 [소수찾기]

이 문제의 핵심은 크게 아래와 같이 볼 수 있다.

1. 숫자 조합하기 👉 🥭순열 Permutation
2. 소수 찾기

✅ 문제 풀이

1. 문제에서 주어지는 문자열을 numbers.split("") 을 통해 배열로 만든다.
2. permutation() 메소드와 swap() 메소드를 통해 모든 숫자들의 조합을 구하고, Set 에 담아서 중복을 제거한다.
3. findPrimeNumber() 메소드를 사용해서 소수를 찾는다. (소수이면 true, 아니면 false 를 반환)

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

class Solution {
		
		static String[] arr;
		static Set<Integer> set = new HashSet<Integer>();

		public int solution(String numbers) {
				int answer = 0;
				arr = numbers.split("");

				// 숫자 조합하기
				for (int i = 1; i <= arr.length; i++) {
						permutation(0, arr.length, i);
				}

				// 소수 count	
				for (int num : set) {
						if(findPrimeNumber(num)) answer++;
				}		
				
				return answer;
		}

		// 순열 만들기(1) : r은 조합할 수의 개수 
		static void permutation(int depth, int n, int r) {
				if(depth == r) {
						// 조합한 숫자 Set에 저장(중복 제거)
						String num = "";
						for(int i = 0; i < r; i++) {
								num += arr[i];
						}
						set.add(Integer.parseInt(num));
						return;
				}

				for (int i = depth; i < n; i++) {
						swap(depth, i);
						permutation(depth+1, n, r);
						swap(depth, i);
				}
		}

		// 순열 만들기(2) - swap
		static void swap(int depth, int index) {
				String temp = arr[depth];
				arr[depth] = arr[index];
				arr[index] = temp;
		}

		// 소수 찾기
		static boolean findPrimeNumber(int num) {
				if(num <= 1) return false;
				for (int i = 2; i * i <= num; i++) {
						if(num % i == 0) return false;	
				}
				return true;
		}
}