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

1. 문제 풀이 아이디어

• 재귀를 활용하여 만들 수 있는 모든 숫자를 생성하고, 이를 Set에 저장한 뒤, 각 숫자가 소수인지 판별하여 해결한다.

2. 나의 정답 코드

class Solution {
    Set<Integer> set = new HashSet<>();

    public int solution(String numbers) {
        int answer = 0;
        addSet("", numbers);
        System.out.println(set);
        for (int i : set) {
            if (isPrime(i))
                answer++;
        }
        return answer;
    }

    public void addSet(String s, String ss) {
        if (!s.isEmpty()) {
            set.add(Integer.parseInt(s));
        }
        for (int i = 0; i < ss.length(); i++) {
            addSet(s + ss.charAt(i), ss.substring(0, i) + ss.substring(i + 1));
        }
    }

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

3. 정리

• 재귀를 사용하여 문자열의 가능한 모든 조합을 생성하고, 이를 정수로 변환해 Set에 저장한다.

• 중복을 제거한 숫자들을 순회하며, isPrime 메서드를 통해 소수 여부를 판단한다.

• 소수로 판별된 숫자의 개수를 카운트하여 결과값으로 반환한다.