[JAVA] Programmers <완전 탐색 LV2> 소수 찾기

이 문제를 오늘 오전 8시부터 보고 풀기 시작했는데... 처음에는 "17"이라는 문자열이 들어오면, 1부터 17까지의 소수의 개수를 구하는 문제라고 덜컥 생각하고 풀어버려서... 오전 풀이 시간을 날려버렸다... 하하.. 문제는 항상 2번씩 읽읍시다.

 

본질은 "17"이라는 문자열을 받으면 받은 문자열을 한자리 숫자로 쪼갠 뒤, 만들 수 있는 모든 숫자 조합에서 소수를 찾는 문제이다. 

즉, 받은 문자열을 쪼개고, 배열에 넣은 뒤 수열을 구하여 풀어야한다.

수열을 만드는 알고리즘은 직전 포스팅에서 열심히 구현해 놨으니, 이제 쓰기만 하면 된다.

---

package com.choonham;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

class Solution {
	public static Set<Integer> tempSet = new HashSet<>();
	// 수열 생성 후 정수화하여 만들어진 정수 中 중복이 없도록 걸러야하므로 Set 을 이용

	public int solution(String numbers) {
		int answer = 0;
		String[] split = numbers.split("");
		List<String> inputArray = new ArrayList<>();
		List<String> resultArray = new ArrayList<>();

		for (String str : split) {
			inputArray.add(str);
		}
		for (int i = 1; i <= inputArray.size(); i++) { // 1자리 수 부터 만들 수 있는 최대 자리 수까지
			getSequence(inputArray, resultArray, inputArray.size(), i);
		}

		Iterator itr = tempSet.iterator();
		while (itr.hasNext()) {
			int tempInt = (int) itr.next();
			if (getPrimeNum(tempInt)) {
				answer++;
			}
		}
		return answer;
	}

	// 수열 생성
	private static void getSequence(List<String> inputArray, List<String> resultArray, int inputLen, int num) {
		if (num == 0) {
			String tempStr = "";
			for (int i = 0; i < resultArray.size(); i++) {
				tempStr = tempStr + resultArray.get(i);
			}
			tempSet.add(Integer.parseInt(tempStr));
			return;
		}

		for (int i = 0; i < inputLen; i++) {
			resultArray.add(inputArray.remove(i));
			getSequence(inputArray, resultArray, inputLen - 1, num - 1);
			inputArray.add(i, resultArray.remove(resultArray.size() - 1));
		}

	}

	// 소수를 구하는 알고리즘
	private boolean getPrimeNum(int num) {
		boolean isPrime = true;
		if (num == 0 || num == 1)
			return false;
		for (int i = 2; i < num; i++) {
			if (num % i == 0) {
				isPrime = false;
				break;
			}
		}
		return isPrime;
	}
}

핵심적인 내용은 이전 포스팅에서 설명한 수열 구하기이므로, 해당 알고리즘을 이해할 수 있다면, 별다른 어려움 없이 풀이가 가능한 문제였다.

결과는 만족스럽게 나온 거 같다.

 

끝!!!