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

문제 :

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

프로그래머스

 

해결 :

import java.util.*;

class Solution {
    public int solution(String numbers) {
    	// 결과를 저장할 set(중복 제거)
        Set<Integer> primeSet = new HashSet<>();
        // 숫자로 만들 수 있는 모든 순열을 구하고, 소수인 경우 set에 추가
        permutation("", numbers, primeSet);
		// 소수의 개수를 반환
        return primeSet.size();
    }
	
    // 숫자로 만들 수 있는 모든 순열을 재귀적으로 생성하는 메서드 
    private void permutation(String prefix, String str, Set<Integer> primeSet) {
        int len = str.length();
        if (!prefix.equals("")) {
            int num = Integer.parseInt(prefix);
            if (isPrime(num)) {
                primeSet.add(num);
            }
        }
        for (int i = 0; i < len; i++) {
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, len), primeSet);
        }
    }

    private boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

 

 

[ isPrime 메소드 ]

소수를 판별할 때, 주어진 숫자(num)를 2부터 그 제곱근까지의 숫자로 나누어서 나누어 떨어지는지 확인합니다. 이 방법은 일종의 최적화 기법입니다. 왜냐하면 어떤 수의 약수 중 가장 큰 수는 그 수의 제곱근보다 클 수 없기 때문입니다.

예를 들어, 16의 약수를 생각해보면, (1, 16), (2, 8), (4, 4)로써 16의 제곱근인 4를 넘지 않는 약수의 쌍이 있습니다. 그러므로 소수를 판별할 때, 16의 제곱근인 4까지만 나누어 떨어지는지 확인해보면 충분합니다.

 

이 코드에서 i * i <= num 조건은 i <= Math.sqrt(num)과 동일한 의미를 가집니다. 그래서 i를 2부터 num의 제곱근까지 반복하는 것으로 충분합니다. 이 방법을 사용하면 효율적으로 소수를 판별할 수 있습니다.

 

[ permutation 메소드 ]

이 메서드는 숫자로 이루어진 문자열에서 가능한 모든 순열을 만들어냅니다. 재귀 호출을 통해 모든 가능한 조합을 찾는 방식으로 동작합니다.

여기서 prefix는 현재까지 생성된 숫자 조합을 나타내며, str은 아직 사용하지 않은 숫자들의 집합을 나타냅니다. 매번 재귀 호출될 때마다 현재까지 생성된 숫자 조합 prefix에 새로운 숫자를 하나씩 추가해가며 새로운 순열을 만들어냅니다.

예를 들어, "123"이라는 숫자로 이루어진 문자열이 있다면, 처음에는 빈 문자열 ""로 시작하여 첫 번째 숫자인 "1"을 prefix에 추가한 뒤, "23"을 str로 전달하여 다시 재귀 호출합니다. 이런 식으로 숫자를 하나씩 추가해 나가면서 모든 가능한 조합을 만들어낼 수 있습니다.

이해를 돕기 위해 재귀 호출의 동작을 단계별로 나누어 설명하면 다음과 같습니다:

1. 초기에는 빈 문자열 ""로 시작합니다.
2. 첫 번째 숫자를 prefix에 추가한 뒤, 남은 숫자로 재귀 호출합니다.
3. 재귀 호출될 때마다 현재까지 생성된 숫자 조합에 새로운 숫자를 추가하여 새로운 순열을 만들어냅니다.
4. 모든 가능한 순열을 탐색할 때까지 재귀 호출을 반복합니다.

이런 방식으로 모든 가능한 숫자 조합을 만들어내고, 그 중에서 소수인 숫자를 찾아 primeSet에 추가합니다.