[42839] 소수 찾기

✔ 소수 찾기

[프로그래머스 42839]

문제 분석하기

문자열을 쪼갠 후, 만들 수 있는 숫자를 모두 만들어 소수인지 확인

이때 숫자의 첫 번째가 0으로 시작할 경우 제외하기 위해 집합을 사용

예) 011 : 011, 11이 같은 숫자이므로 011 제외

손으로 풀어보기

1. 문자열로 만들 수 있는 숫자를 모두 만들며 소수인지 확인
   • 문자의 길이가 n일 때, 1, 2, 3, ... n자리의 숫자를 생성
   • 예) 17
     "", "17" → "1", "7"
     "", "17" → "7", "1"
     "1", "7" → "17"
     "7", "1" → "71"
   • 소수인지는 에라토스테네스 방법 사용
2. 만들어진 숫자가 소수일 경우 집합에 저장
3. 집합의 크기 반환

슈도코드 작성하기

numbers(각 종이 조각에 적힌 숫자가 적힌 문자열)
set(만들어진 소수 숫자 저장 집합)
숫자 생성 함수 실행
set의 크기 반환

숫자 생성 함수 {
   if(현재 숫자 조합이 공백이 아니라면) {  
       if(숫자가 소수인지 확인하여 true라면) {
           set에 저장
       }
   }
   for(i -> 남은 문자열의 길이) {
       숫자 생성 함수(현재 숫자 조합 + 남은 문자열의 i, 남은 문자열에서 i를 제외한 문자열)
   }
}

소수 확인 함수 {
   0이거나 1이면 false 반환
    for(제곱근까지 반복하기) {
        소수가 아니면 false 반환
    }
    true 반환
}

코드 구현하기

/**
 * 42839) 소수_찾기
 */
public class K003_42839 {
    static Set<Integer> set;

    // numbers(각 종이 조각에 적힌 숫자가 적힌 문자열)
    public int solution(String numbers) {
        // set(만들어진 소수 숫자 저장 집합)
        set = new HashSet<>();
        // 숫자 생성 함수 실행
        makeNumbers("", numbers);
        // set의 크기 반환
        int answer = set.size();
        return answer;
    }

    // 숫자 생성 함수
    private void makeNumbers(String madeNumbers, String remainNumbers) {
        // 현재 숫자 조합이 공백이 아니라면
        if (!madeNumbers.equals("")) {
            int number = Integer.valueOf(madeNumbers);
            // 숫자가 소수인지 확인
            if (isPrime(number)) {
                // set에 저장
                set.add(number);
            }
        }
        // 숫자 생성 함수(현재 숫자 조합 + 남은 문자열의 i, 남은 문자열에서 i를 제외한 문자열)
        for (int i = 0; i < remainNumbers.length(); i++) {
            makeNumbers(madeNumbers + remainNumbers.charAt(i),
                    remainNumbers.substring(0, i) + remainNumbers.substring(i + 1, remainNumbers.length()));
        }
    }

    // 소수 확인 함수
    private boolean isPrime(int number) {
        // 0이거나 1이면 소수가 아님
        if (number == 0 || number == 1) {
            return false;
        }
        // 에라토스테네스의 체 이용
        // 제곱근까지 반복하기
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                // 소수가 아니면 false 반환
                return false;
            }
        }
        // true 반환
        return true;
    }

    public static void main(String[] args) {
        K003_42839 solution = new K003_42839();

        String numbers = "17";

        int result = solution.solution(numbers);

        System.out.println(result);
    }
}