프로그래머스_완전탐색_소수 찾기 (JAVA)

문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.   제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.     입출력 예입출력 예 설명   예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다. 11과 011은 같은 숫자로 취급합니다.

 

 

 

주어진 문자열에 포함된 숫자를 모두 조합해서 소수인지 아닌지 판단하는 문제입니다. "모든 조합수(경우의 수)"는 순열을 의미하기 때문에 순열 알고리즘을 사용해야 합니다. 조합과 순열, 멱집합을 응용하는 문제가 많으니 해당 알고리즘들을 잘 파악해두는게 좋을 듯합니다. 구현 방식은 정말 다양한데 아래 글들은 제 스타일대로 구현한 코드들입니다. 재귀함수의 원리만 알면 다른 방식들도 쉽게 이해할 수 있을 것 같습니다.

 

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_멱집합 알고리즘 (JAVA)

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_순열 알고리즘 (JAVA)

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_조합 알고리즘 (JAVA)

 

 

---

 

순열 알고리즘으로 모든 경우의 수만 구하면 나머지는 간단히 해결할 수 있습니다. 0이 가장 앞에 있는 부분집합만 걸러내준 뒤, 부분집합을 모두 더해 하나의 숫자로 만들어 소수인지 아닌지 판별해 소수일 경우 count를 올려주면 됩니다.

 

그리고 "11"의 경우 {1, 1}, {1, 1}이 두 번 나오게 됩니다. "111"의 경우 세 번이 중복되겠죠. 중복은 카운트에 올리면 안되니 Set 컬렉션을 사용해 하나의 숫자가 나올 때 넣어둔 뒤 새로운 숫자는 Set에 있는지 먼저 확인한 뒤 소수 판별을 진행하면 됩니다. 경우의 수가 많아지면 Set에서 검색하는 빈도수가 많아질테니 HashSet보다는 정렬해서 저장하는 TreeSet이 더 적합할 듯합니다. TreeSet은 저장할 때는 좀 더 오래걸리지만 검색할 때는 더 빠릅니다.

 

마지막으로 소수는 제곱근까지만 나눠보면 됩니다. 이건 그냥 똑똑한 수학자들이 증명해둔 것이므로 그냥 그렇게 사용하고 있습니다. ㅎㅎ

 

package pojoPrj;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.TreeSet;

class Solution {

	private TreeSet<String> set = new TreeSet<>();
	private int count;

	public static void main(String[] args) {

		String numbers = "11112";
		Solution s = new Solution();
		System.out.println(s.solution(numbers));

	}

	public int solution(String numbers) {

		int size = numbers.length();

		// 리스트에 담아줌
		List<Character> arr = new ArrayList<>();
		for (int i = 0; i < size; i++) {
			arr.add(numbers.charAt(i));
		}

		// 결과를 저장할 리스트
		List<Character> result = new ArrayList<>();

		// nPr에서 r을 계속 늘리면서 순열 알고리즘 수행
		for (int i = 0; i < size; i++) {
			permutation(arr, result, size, i + 1);
		}

		return count;
	}

	/**
	 * 소수 판별
	 * 
	 * @param n : 판별할 숫자
	 * @return
	 */
	private boolean isPrime(int n) {

		int i;
		int sqrt = (int) Math.sqrt(n);

		// 2는 유일한 짝수 소수
		if (n == 2)
			return true;

		// 짝수와 1은 소수가 아님
		if (n % 2 == 0 || n == 1)
			return false;

		// 제곱근까지만 홀수로 나눠보면 됨
		for (i = 3; i <= sqrt; i += 2) {
			if (n % i == 0)
				return false;
		}

		return true;
	}

	/**
	 * 순열 알고리즘
	 * 
	 * @param arr    : 원본 리스트
	 * @param result : 결과 담을 리스트
	 * @param n      : 전체 갯수
	 * @param r      : 선택할 갯수
	 */
	public void permutation(List<Character> arr, List<Character> result, int n, int r) {

		if (r == 0) {

			// 0으로 시작하는 부분집합은 제외
			if (result.get(0) != '0') {

				String str = "";
				int size = result.size();
				for (int i = 0; i < size; i++) {
					str += result.get(i);
				}

				int num = 0;

				// 이미 나온 숫자 조합이 아닐 경우
				if (!set.contains(str)) {
					num = Integer.parseInt(str);
					set.add(str);

					// 소수 판별
					if (isPrime(num)) {
						System.out.println(num);
						count++;
					}
				}
			}

			return;
		}

		for (int i = 0; i < n; i++) {

			result.add(arr.remove(i));
			permutation(arr, result, n - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}

	}
}