[programmers] 소수 찾기 - Java

소수 찾기

문제 설명

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

입출력 예 설명

• 11과 011은 같은 숫자로 취급합니다.

solution.java

import java.util.*;

class Solution {
    public int solution(String numbers) {
        Set<Integer> primes = new HashSet<>();
        
        // numbers의 모든 순열 생성
        generatePermutations("", numbers, primes);

        // 소수의 개수 카운트
        int count = 0;
        for (int num : primes) {
            if (isPrime(num)) {
                count++;
            }
        }

        return count;
    }
    
    // 순열 생성하는 함수
    private void generatePermutations(String prefix, String remaining, Set<Integer> primes) {
        if (!prefix.isEmpty()) {
            primes.add(Integer.parseInt(prefix));
        }

        for (int i = 0; i < remaining.length(); i++) {
            generatePermutations(prefix + remaining.charAt(i),
                                  remaining.substring(0, i) + remaining.substring(i + 1),
                                  primes);
        }
    }
    
    // 소수인지 판별하는 함수
    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;
    }
}

핵심 키워드

• 순열 생성 함수
• prefix가 비어 있지 않으면 정수로 변환하여 Set에 추가한다. 이를 통해 길이에 관계없이 모든 숫자를 추가할 수 있다.
• 나머지 문자열의 각 숫자를 substring한 후, prefix와 합쳐가며 새로운 수를 만든다.
• 이후 수정된 문자열을 다음 재귀 호출에 전달한다.

• 소수 판별 함수
• 2부터 num의 제곱근까지 반복하고, num % i == 0인 경우 소수가 아니다.

결론!