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

문제

프로그래머스-소수 찾기
string으로 된 숫자를 한 자리 단위로 짜른 다음 조합해서 나오는 수 중 소수의 개수를 구하는 문제.
“011”라면 0,1,11,110,101 을 만들 수 있다.

풀이

(1) 소수 만들기
이 중 소수는 11, 101이다. 우선 소수를 구하기 위해 미리 배열을 만들었다.(에라토스테네스의 체 이용)
우선 입력받은 문자열이 3자리면 (3+1)^10해서 소수 배열의 사이즈를 10000으로 만든다음 반복문을 돌면서 소수가 아닌 인덱스의 칸에 true를 넣는다.
(2) 조합해서 숫자만들기
0부터 시작한다. 반복문을 돌면서 사용중이 아닌 자리의 수를 사용처리하고 해당 숫자를 붙여서 다음 차례로 숫자로 넘긴다.(이게 무슨말이야 ㅠㅠ)
예) 17인 경우, 반복문을 돌려서 0 시작,
반복문해서 1을 먼저 사용처리하고 (010)+1 해서 반복
1 시작, 반복문으로 7 사용처리하고 (110)+7 해서 반복
17시작, 소수니까 set에 넣고 반복문
그런데 더이상 사용중이 아니면서 넘길게 없어, 종료
1 종료
7 시작 … …

소스코드

import java.util.HashSet;

class Solution {
	char[] n;
	boolean[] chk;
	int answer;
	boolean sosu[];

	HashSet<Integer> set = new HashSet<>();

	public int solution(String numbers) {
		n = numbers.toCharArray();
		int size = (int) Math.pow(10, n.length+1);
		sosu = new boolean[size];
		chk = new boolean[n.length];
		setSosu();
		subsum(0);

		return set.size();
	}
// (2)
	private void subsum(int idx) {
		// TODO Auto-generated method stub
		if (!sosu[idx]) {
			set.add(idx);
		}
		for (int i = 0; i < chk.length; i++) {
			if (!chk[i]) {
				chk[i] = true;
				subsum(idx * 10 + (n[i] - '0'));
				chk[i] = false;
			}
		}
	}

// (1)
	private void setSosu() {
		// TODO Auto-generated method stub
		sosu[0] = true;
		sosu[1] = true;
		for (int i = 2; i <= Math.ceil(Math.sqrt(sosu.length)); i++) {
			for (int j = i + i; j < sosu.length; j = j + i) {
				sosu[j] = true;
			}
		}
	}
}

다른사람의 코드

string으로 순열을 다루는게 생각치도 못한 방법이라 신기하고 java를 잘다루는게 이런건가 싶다.. 깔끔하면서도 라이브러리를 잘 활용할 수 있기를 ㅠㅠ

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

        public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}