소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항 

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

 

문제 회고

 

코드

import java.util.*;
 
 
class Solution {
    
    final int MAX = 10000000;        
    int len = 0;
    HashSet<Integer> set = new HashSet<>();
    String[]  strNums = null;
    boolean[] visited = null;
    boolean[] primeList = new boolean[MAX];
    
    
    // 종이 조각으로 만들 수 있는 모든 경의우의 소수를 구한다.
    public void getResult(int x, String strNum) {
        
        // 소수판별
        if ( strNum != "") {
            int num = Integer.parseInt( strNum );
            if ( !primeList[num] ) set.add( num );
        } 
        
        // 기저조건
        if ( x >= len ) return; 
        
        // 다음 차례 진행
        for ( int i = 0; i < len; ++i ) { 
            if ( visited[i] ) continue; // 한번 사용된 요소는 다시 사용하면 안되므로 필터링해준다.
            visited[i] = true;
            getResult( x+1, strNum + strNums[i] );
            visited[i] = false; 
        }
        
    }
    
    
    // main
    public int solution(String numbers) {
 
        // 에라토스테네스의 체 : 한번에 소수를 미리 구해둔다.
        // false : 소수, true : 소수아님
        primeList[0] = true;
        primeList[1] = true;
        for ( int i = 2; i < MAX; ++i ) {
            for ( int j = i + i; j < MAX; ) {
                primeList[j] = true;
                j += i;
            }
        }
         
        // 초기화 
        strNums = numbers.split("");
        len = strNums.length;
        visited = new boolean[len];
        
        // 연산을 시행한다.
        getResult( 0, "" ); 
        
        // 정답
        return set.size();
    }
}