📝 소수찾기 (Level 2)

완전탐색
소수찾기

🔹Python

문자열 numbers에 있는 문자들을 하나씩 가져와서 조합을 해
-> 다시 int로 바꿔서 소수인지 판단해

조합을 어떻게 할 것인가 ... ? 경우의 수 -> 각 문자(숫자)가 있거나 없거나 2^n
그럼 배열에 넣고 빼기? push/pop? 이건 아닌데

찾아보니 파이썬에 순열(permutations)함수가 있다. 이걸 사용하면 되겠다. 그리고 level1에 소수찾는 문제가 있었어서 에라스토테네스의 체 알고리즘을 알고 있었다. 그래서 구현하려고 했는데 .. 머리가 안돌아가서 다른 사람 풀이 참고했다ㅜ

• 다른 사람의 풀이

from itertools import permutations

# 소수 판별법 : 에라스토테네스의 체
def checkPrime(n):
    if n < 2 :
        return False
    
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    
    return True

def solution(numbers):
    answer = []
    numbers = list(numbers)
    tmp = []
    
    for i in range(1, len(numbers)+1):
    	#permuntations 객체의 쌍을 list로 변환
        tmp += list(permutations(numbers, i))
       
       
    # tmp에 있는 list들을 join함수를 이용해 결합 후 int형으로 변환
    num = [int(''.join(t)) for t in tmp]
    
    for i in num:
        if checkPrime(i): 
            answer.append(i)
            
    # 중복된 숫자 제거위해 set함수 사용            
    return len(set(answer)) 

list로 묶고 join으로 int 변환하고 이런 것들 어떻게 생각하는거지ㅜ 익숙해지는게 답이 겠지 .. ? 🥹 이걸 자바로는 어떻게 하지 ㅜㅅㅜ

---

🔸Java

• 다른 사람의 풀이

import java.util.HashSet;

class Solution {
    // solution 함수: 주어진 문자열에서 소수의 개수를 반환합니다.
    public int solution(String numbers) {
        // 모든 가능한 숫자 순열을 저장하기 위한 HashSet
        HashSet<Integer> set = new HashSet<>();
        // 순열을 생성하고 set에 저장하는 메소드 호출
        permutation("", numbers, set);
        int count = 0;

        // HashSet에서 각 숫자를 순회하며 소수 판별
        while(set.iterator().hasNext()){
            int a = set.iterator().next(); // HashSet에서 하나의 숫자를 가져옵니다.
            set.remove(a); // 중복 방지를 위해 가져온 숫자를 HashSet에서 제거합니다.
            
            // 숫자가 2인 경우 소수로 간주
            if(a == 2) {
                count++;
            }
            // 홀수이며 소수인 경우 소수 개수를 증가시킵니다.
            else if(a % 2 != 0 && isPrime(a)){
                count++;
            }
        }
        // 최종적으로 소수의 개수를 반환합니다.
        return count;
    }

    // 소수 판별 함수
    public boolean isPrime(int n){
        // 0 또는 1은 소수가 아닙니다.
        if(n == 0 || n == 1) return false;

        // 2 이상의 소수는 홀수만을 고려합니다.
        // 2부터 n의 제곱근까지 나누어 떨어지는 것이 있는지 확인
        for(int i = 3; i <= (int)Math.sqrt(n); i += 2){
            if(n % i == 0) return false;
        }
        return true; // 나누어 떨어지는 것이 없으면 소수입니다.
    }

    // 문자열의 순열을 생성하여 HashSet에 저장하는 함수
    public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        // prefix가 비어있지 않은 경우 HashSet에 추가합니다.
        if (!prefix.equals("")) {
            set.add(Integer.valueOf(prefix));
        }
        // 문자열의 각 문자에 대해 순열을 재귀적으로 생성합니다.
        for (int i = 0; i < n; i++) {
            // 현재 문자(str.charAt(i))를 prefix에 추가하고,
            // 나머지 문자열에서 현재 문자를 제거한 부분을 사용하여 순열 생성
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), set);
        }
    }
}

코드 설명

• solution 함수:
  주어진 문자열 numbers에서 모든 가능한 숫자 순열을 생성하고, HashSet에 저장합니다. 각 숫자를 순회하며 소수인지 확인하고, 소수인 경우 카운트를 증가시킵니다. 최종적으로 소수의 개수를 반환합니다.

• isPrime 함수:
  입력된 숫자가 소수인지 판별합니다. 0과 1은 소수가 아니며, 2 이상의 홀수 숫자만 소수로 판별합니다. 제곱근까지 나누어 떨어지는 것이 없으면 소수로 간주합니다.

• permutation 함수:
  문자열 str의 모든 가능한 순열을 생성합니다. 현재까지의 순열을 prefix에 추가하고, 이를 HashSet에 저장합니다. 재귀적으로 문자열의 각 문자에 대해 순열을 생성합니다. 문자열에서 현재 문자를 제거한 나머지 문자열로 순열을 계속 생성합니다.

오 봐도 이해가 안가..