[문제풀이] 소수 찾기

업데이트:

문제 링크 : 소수 찾기

풀이 시간 : 20분

1. 문제 풀이

조합과 소수를 활용한 문제 풀이

1) 입력으로 만들 수 있는 가장 큰 수를 찾는다(입력을 내림차순 정렬)

2) 가장 큰 수 이하의 소수를 찾는다.(에라토스테네스의 체)

3) 입력으로 만들 수 있는 수 모든 경우를 찾는다(조합)

4) 각 경우가 소수인지 판별 후 HashSet에 넣어서 중복 처리를 해준다.

2. 소스 코드

    // 조합에 필요한 visit 배열
	static boolean[] v;
	// 찾으면 소수 넣은 HashSet
	static HashSet<Integer> hs;
	// 소수 배열
	static boolean[] prime_number;
	static public int solution(String numbers) {
        int answer = 0;
        hs = new HashSet<Integer>();
        v = new boolean[numbers.length()];
        // 입력 배열의 조합의 최대값
        // 소수 배열 크기 정하기 위해서
        char[] temp = numbers.toCharArray();
        Arrays.sort(temp);
        int sum = 0;
        for (int i = temp.length-1; i >=0; i--) {
			sum = sum*10+(temp[i]-'0');
		}
        prime_number = new boolean[sum+1];
        prime_number[0] = true;
        prime_number[1] = true;
        // 에라토스테네스의 체를 이용하여 소수 배열 
        for (int i = 2; i <= Math.sqrt(prime_number.length); i++) {
			if(!prime_number[i]) {
				for (int j = i+i; j < prime_number.length; j=j+i) {
					prime_number[j] = true;
				}
			}
		}
        // 조합을 통해 모든 경우의 수 찾기
        combi(numbers,0);
        // 구한 소수의 갯수
        answer = hs.size();
        return answer;
    }
	static void combi(String numbers,int cnt) {
		// 소수 판별
		if(!prime_number[cnt]) {
			hs.add(cnt);
		}
		// 조합 구하기
		for (int i = 0; i < numbers.length(); i++) {
			if(!v[i]) {
				v[i] = true;
				combi(numbers, cnt*10+( numbers.charAt(i)-'0'));
				v[i] = false;
			}
		}
	}

3. 후기

단순히 제한 사항의 최대 값만큼 소수를 계속 찾는 것보다(시간 초과 안 뜸)

입력으로 만들 수 있는 최대 값을 구해서 최대 값 이하까지만 구한다

참고