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

문제

소수 찾기

문제 풀이

1. 숫자를 하나씩 분리한다.
2. 분리된 숫자들로 만들 수 있는 모든 경우의 수를 구한다.
3. 소수인지 판별한다.

큰 틀로 보면 위와 같은데, 구현이 상당히 오래 걸린 문제이다. 숫자를 분리하는 것은 charAt으로 하나씩 떼어내고 int 형으로 저장했고, 배열을 정렬한 뒤 배열을 토대로 모든 경우의 수를 구하는 combination 메소드를 구현했다.

그 다음 당연히 중복되는 숫자가 존재하는데, Treeset에 저장해서 중복숫자를 제거했다. Treeset에 존재하는 숫자들이 모든 경우의 수인데 이것을 토대로 소수체크를 하면된다.

소수 체크는 에라토스테네스의 체를 이용하여 풀었다.

프로그램 코드

import java.util.*;
class Solution {
    int[] num;
	TreeSet<Integer> set;
	boolean[] visited;
	int answer = 0;
    String numbers="";
    
    public int solution(String numbers) {
    num = new int[numbers.length()];
	set = new TreeSet();
	visited = new boolean[num.length];
    this.numbers = numbers;
        
        for (int i = 0; i < num.length; i++) { // num배열에 숫자 하나씩 뜯어서 저장
			num[i] = numbers.charAt(i) - '0';
		}

		Arrays.sort(num);// 오름차순 정렬

		for (int i = 0; i < numbers.length(); i++) { // 숫자 조합 구하기
			int[] list = new int[i + 1];
			combination(0, i + 1, -1, list);
		}

		boolean[] prime = new boolean[set.last() + 1];
		prime[0] = prime[1] = true;
		// 소수 체크
		for (int i = 2; i <= Math.sqrt(set.last()); i++) {
			if (prime[i])
				continue;
			for (int j = i + i; j <= set.last(); j += i) {
				prime[j] = true;
			}
		}
		for(Integer i : set) {
			if(!prime[i])
				answer++;
		}
        
        return answer;
    }
    
    void combination(int depth, int length, int com, int[] list) {
		if (depth == length) { // 종료 지점
			String tmp = "";
			for (int i = 0; i < list.length; i++) {// list에 들어있는 숫자 붙여서 set에 저장
				tmp += list[i];
			}
			set.add(Integer.parseInt(tmp));
			return;
		}

		for (int i = 0; i < numbers.length(); i++) {
			if (!visited[i]) {
				visited[i] = true;
				list[depth] = num[i];// list에 저장
				combination(depth + 1, length, i, list);
				visited[i] = false;
			}

		}
	}
}