문제 22 - 소수 찾기 (Python)

프로그래머스

주어진 숫자 카드들을 조합하여 만들 수 있는 모든 수 중에서 소수가 몇 개인지를 찾는 문제입니다. 순열을 생성하는 완전 탐색 기법과 효율적인 소수 판별 알고리즘을 결합하여 해결할 수 있습니다.

---

1.  나의 풀이

 

from itertools import permutations

def is_prime(num):
    # 2 미만의 숫자는 소수가 아닙니다.
    if num < 2:
        return False
    
    # n의 제곱근까지만 약수 여부를 확인하여 성능을 최적화합니다.
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    nums = set()
    
    # 1. 가능한 모든 순열 생성 (1글자부터 n글자까지)
    for l in range(1, len(numbers) + 1):
        for permutation in permutations(numbers, l):
            # 생성된 튜플을 문자열로 합친 뒤 정수로 변환하여 set에 추가합니다.
            nums.add(int(''.join(list(permutation))))

    # 2. 생성된 모든 숫자들에 대해 소수 판별을 수행합니다.
    for num in nums:
        if is_prime(num):
            answer += 1
            
    return answer

---

2.  오늘 배운 점 및 복기 노트

제곱근 \( \sqrt{n} \) 까지만 약수를 확인하는 이유
어떤 수 \( n \) 이 \( a \times b \) 로 이루어져 있다면, \( a \) 와 \( b \) 중 적어도 하나는 반드시 \( \sqrt{n} \) 보다 작거나 같습니다. 예를 들어 36의 약수를 찾을 때 \( \sqrt{36} = 6 \) 이므로, 6까지만 나누어 보면 그 이상의 약수 존재 여부를 논리적으로 확신할 수 있습니다. 이를 통해 반복 횟수를 \( O(n) \) 에서 \( O(\sqrt{n}) \) 으로 크게 줄일 수 있습니다.

에라토스테네스의 체 활용 시점
범위 내의 모든 소수를 한꺼번에 구해야 할 때는 에라토스테네스의 체가 효율적입니다. 하지만 이번 문제처럼 판별해야 할 숫자의 개수가 상대적으로 적고 숫자의 범위가 큰 경우에는 개별적으로 제곱근 판별법을 사용하는 것이 메모리 관리 측면에서 유리합니다.

에라토스테네스의 체 코드

def get_eratosthenes(max_n):
    # 0과 1은 소수가 아니므로 False로 초기화합니다.
    sieve = [False, False] + [True] * (max_n - 1)
    
    for i in range(2, int(max_n**0.5) + 1):
        if sieve[i]:
            # i가 소수라면 i의 배수들을 모두 제거합니다.
            for j in range(i*i, max_n + 1, i):
                sieve[j] = False
    return sieve

소수 판별 알고리즘 선택 기준
10만 이하의 범위에서 여러 숫자를 반복적으로 비교해야 한다면 에라토스테네스의 체 방식을 사용합니다. 단순히 특정 숫자가 소수인지만 판별하거나 숫자의 범위가 매우 크다면 제곱근까지 약수가 있는지만 확인하는 방식을 사용하는 것이 적절합니다.

---

3. 프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

순열 생성 시의 중복 제거
itertools.permutations는 동일한 숫자가 포함되어 있어도 인덱스가 다르면 다른 순열로 간주하여 반환합니다. 이를 set 자료구조에 담음으로써 "011"과 "11"처럼 숫자로 변환했을 때 같아지는 경우와 중복 생성된 값들을 효율적으로 처리할 수 있습니다.

2차원 배열 Flatten 기법
교재에서는 여러 길이의 순열 결과를 하나의 리스트로 합치기 위해 리스트 컴프리헨션을 활용한 2차원 배열 압축 기법을 제시합니다. num = [int(''.join(y)) for x in num for y in x]와 같은 방식을 사용하면 코드를 더 간결하게 작성할 수 있습니다.

거듭제곱 연산자를 이용한 제곱근 계산
math.sqrt() 함수를 임포트하지 않고도 num 0.5를 사용하여 간결하게 제곱근을 구할 수 있습니다. 이는 알고리즘 테스트 환경에서 라이브러리 의존성을 줄이는 유용한 방법입니다.