Programmers | Level 2 | 소수 찾기

Programmers | Level 2 | 소수 찾기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Brute Force

󰧭 Description

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 Constraints

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

󰦕 Examples

numbers	return
"17"	3
"011"	2

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int solution(String numbers) {
        Set<Integer> primes = new HashSet<>();  // 중복된 소수를 제거하기 위해 Set 사용
        permute("", numbers, primes);  // 모든 가능한 숫자 조합을 생성하고 소수 판별

        return primes.size();  // Set의 크기가 곧 소수의 개수
    }

    // 순열을 생성하고 소수를 판별하는 재귀 함수
    private void permute(String current, String rest, Set<Integer> primes) {
        // 현재 조합된 숫자가 비어 있지 않으면 숫자로 변환하여 소수 여부를 판별
        if (!current.isEmpty()) {
            Integer number = Integer.parseInt(current);
            if (isPrime(number)) primes.add(number);  // 소수라면 Set에 추가 (중복 방지)
        }

        // 남은 문자들로 순열을 생성
        for (int i = 0; i < rest.length(); i++) {
            String nextPrefix = current + rest.charAt(i);  // 현재 문자 추가
            String nextRest = rest.substring(0, i) + rest.substring(i + 1);  // 현재 문자를 제외한 나머지
            permute(nextPrefix, nextRest, primes);  // 재귀 호출로 다음 순열 생성
        }
    }

    // 소수 판별 함수
    private boolean isPrime(Integer num) {
        if (num <= 1) return false;  // 1 이하의 숫자는 소수가 아님
        if (num == 2) return true;   // 2는 유일한 짝수 소수
        if (num % 2 == 0) return false;  // 짝수는 소수가 아님
        // 소수를 효율적으로 판별하기 위해 홀수만 검사
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;  // 소수가 아닌 경우
        }
        return true;  // 나누어 떨어지지 않으면 소수
    }
}

 Approach

이 문제는 주어진 숫자로 만들 수 있는 모든 순열을 생성하고, 그 중에서 소수인 조합을 찾아내는 완전 탐색(Brute Force) 문제입니다. 핵심은 모든 가능한 숫자 조합을 생성한 뒤, 각 조합이 소수인지 확인하는 과정입니다.

1. 문제 분석

주어진 numbers 문자열에서 만들 수 있는 모든 숫자 조합을 생성하고, 그중 소수인 숫자를 찾아야 합니다. 이를 위해 순열 생성과 소수 판별이라는 두 가지 주요 작업이 필요합니다.

• 순열(Permutation): 순열은 주어진 요소들의 모든 가능한 순서를 의미합니다. 예를 들어, 숫자 123의 순열은 123, 132, 213, 231, 312, 321과 같이 다양한 조합이 될 수 있습니다. 순열은 조합 가능한 모든 경우의 수를 고려하기 때문에, 모든 가능성을 탐색해야 할 때 유용합니다.
• 소수(Prime Number): 소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 예를 들어, 2, 3, 5, 7과 같은 수가 소수에 해당합니다. 소수는 수학에서 중요한 개념으로, 특정 알고리즘의 복잡도를 결정짓는 중요한 요소가 됩니다.

문자열이 주어졌을 때, 이를 숫자로 변환하여 각 조합이 소수인지 확인해야 합니다.

2. 접근 방식

• 모든 순열 생성:
  • 순열은 주어진 원소들의 순서를 바꾸어 나올 수 있는 모든 가능한 경우를 말합니다.
  • 이 문제에서는 주어진 숫자 문자열을 조합하여 가능한 모든 숫자를 생성하고, 그 숫자의 모든 순열을 구합니다.
  • 재귀 함수를 사용하여 이러한 모든 가능한 순열을 생성할 수 있습니다.
  • 각 순열은 하나의 숫자로 취급되며, 이 모든 조합을 소수 판별을 위해 사용합니다.
• 소수 판별:
  • 생성된 순열을 숫자로 변환하고, 해당 숫자가 소수인지 확인합니다.
  • 소수 여부를 판별하기 위해 제곱근까지만 검사를 수행하여 효율성을 높입니다.
• 중복 제거:
  • 동일한 숫자 조합이 여러 번 나올 수 있기 때문에, 중복을 제거할 필요가 있습니다.
  • Set 자료구조를 사용하여 중복을 제거하며, 소수의 고유한 조합만을 카운트합니다.

3. 순열 생성 함수 구현

이 문제의 핵심은 재귀적으로 모든 가능한 순열을 생성하는 것입니다.

// 순열을 생성하는 재귀 함수
private void permute(
        String current, // 현재까지 생성된 숫자 조합
        String rest,  // 아직 사용되지 않은 숫자들
        Set<Integer> permutations  // 생성된 숫자 조합을 저장할 Set
) {
    // current가 비어 있지 않으면 숫자로 변환하여 Set에 추가
    if (!current.isEmpty()) {
        Integer number = Integer.parseInt(current);
        permutations.add(number);  // 새로운 숫자 조합을 Set에 추가
    }

    // 남은 문자들로 순열을 생성
    for (int i = 0; i < rest.length(); i++) {
        String nextPrefix = current + rest.charAt(i);  // 현재 문자 추가
        String nextRest = rest.substring(0, i) + rest.substring(i + 1);  // 현재 문자를 제외한 나머지
        permute(nextPrefix, nextRest, permutations);  // 재귀 호출로 다음 순열 생성
    }
}

• 순열 생성: 이 재귀 함수는 현재까지 선택된 문자 조합 current와 남은 문자 rest를 인자로 받아, 가능한 모든 순열을 생성합니다.
• 소수 판별: 각 재귀 호출이 끝날 때마다 current 값을 숫자로 변환해 소수인지 판별합니다. 소수인 경우 Set에 추가됩니다.

이 함수는 주어진 숫자 문자열로부터 가능한 모든 순열을 생성하여 각 순열을 숫자로 변환한 뒤, 이를 Set<T>에 저장하는 역할을 합니다. Set<T>에 저장된 모든 숫자 조합은 중복이 제거된 상태로 유지됩니다.

4. 소수 판별 함수 구현

생성된 숫자 조합이 소수인지 여부를 판단하기 위해 소수 판별 함수를 구현합니다.

// 소수 판별 함수
private boolean isPrime(int n) {
    if (n <= 1) return false;  // 1 이하의 숫자는 소수가 아님
    if (n == 2) return true;   // 2는 유일한 짝수 소수
    if (n % 2 == 0) return false;  // 짝수는 소수가 아님
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;  // 소수가 아닌 경우
    }
    return true;  // 나누어 떨어지지 않으면 소수
}

소수 판별 과정은 다음과 같습니다:

• 1 이하의 숫자: 1 이하의 숫자는 소수가 아니기 때문에 false를 반환합니다.
• 2는 유일한 짝수 소수: 2는 유일하게 짝수 중에서 소수이므로, 예외적으로 true를 반환합니다.
• 짝수는 소수가 아님: 2를 제외한 모든 짝수는 소수가 아니므로, 이 경우 false를 반환합니다.
• 홀수만 검사: 그 이후의 숫자들은 홀수만 검사하여 효율적으로 소수를 판별합니다. 이는 짝수는 이미 소수가 아님을 확인했기 때문에 연산을 줄이기 위한 방법입니다.
• 제곱근까지만 검사: 숫자가 소수인지 판별할 때, 제곱근까지만 검사하면 됩니다. 이는 수학적으로 어떤 수가 소수가 아닌 경우, 그 수의 제곱근보다 작은 약수를 반드시 가지기 때문입니다. 따라서 i * i <= n 조건을 사용하여 제곱근까지만 반복문을 실행합니다.

이러한 최적화된 소수 판별 알고리즘을 통해 생성된 모든 숫자 조합에 대해 빠르게 소수 여부를 판단할 수 있습니다.

5. 소수 카운트

모든 순열을 생성한 후, 소수인 조합을 Set<T>에 저장하여 중복을 제거한 뒤, 최종적으로 소수의 개수를 카운트합니다.

int result = 0;
for (Integer permutation : permutations) {
    if (isPrime(permutation)) result++;
}

현재 접근 방식에서는 순열을 모두 생성한 후에 소수 판별을 별도로 진행하고 있지만, 순열을 생성하는 재귀 과정에서 소수만을 판별하여 저장하는 방법도 가능합니다. 이를 통해 중복을 제거하면서 동시에 소수를 필터링할 수 있어 효율성을 높일 수 있습니다.

6. 최종 결과 반환

모든 가능한 숫자 조합을 생성하고 소수를 판별한 후, 소수의 개수를 반환합니다.

Set<Integer> primes = new HashSet<>();  // 중복된 소수를 제거하기 위해 Set 사용
permute("", numbers, primes);  // 모든 가능한 숫자 조합을 생성하고 소수 판별

return primes.size();  // Set의 크기가 곧 소수의 개수

󰄉 Complexity

• ⏳ TC: O(n!)
• 💾 SC: O(n)

이 문제는 순열을 생성하는 과정에서 O(n!)의 시간 복잡도를 가지며, 순열의 개수와 숫자 조합을 저장하기 위한 공간 복잡도는 O(n)입니다. 이 문제는 주어진 숫자들로 만들 수 있는 모든 소수를 찾는 문제로, 재귀 호출과 소수 판별을 효율적으로 구현하는 것이 핵심입니다.