99클럽 코테 스터디 23일차 TIL - 완전탐색(프로그래머스- 소수찾기)

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

• 오늘의 학습 키워드 : 완전탐색
• 공부한 내용
  • 여러 개의 소수를 구해야 한다면? 에라토스테네스의 체를 사용.
  • 단일 숫자의 소수 여부를 판별한다면? 간단한 나눗셈 방식을 사용
    (숫자 n에 대해 2부터 √n까지 나눠보고, 나누어떨어지지 않으면 소수.)

즉, 이문제는 숫자 조합의 범위가 그렇게 크지 않으므로 간단한 나눗셈 방식으로 사용해도 괜찮다..

1️⃣ 간단한 나눗셈 방식 사용한 경우

def is_prime(n):
    """소수 판별 함수: 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):
    """numbers로 만들 수 있는 소수의 개수를 반환"""
    # 중복 방지를 위해 set 사용
    unique_numbers = set()

    # 모든 조합 생성 (재귀 방식)
    def generate_numbers(current, remaining):
        if current:  # 숫자가 생성되었을 경우만 추가
            unique_numbers.add(int(current))
        for i in range(len(remaining)):
            generate_numbers(current + remaining[i], remaining[:i] + remaining[i+1:])

    # 재귀 호출로 모든 조합 생성
    generate_numbers("", list(numbers))

    # 소수의 개수 계산
    return sum(1 for num in unique_numbers if is_prime(num))

2️⃣ 에라토스테네스의 체 사용

에라토스테네스의 체
작은 숫자부터 시작해, 그 숫자의 배수를 모두 지웁니다.
지워지지 않고 남은 숫자들은 모두 소수
시간 복잡도: O(n log log n)

예제 (n=10에서 소수를 찾기)

1. 초기 배열: [2, 3, 4, 5, 6, 7, 8, 9, 10]
2. 2의 배수 제거: [2, 3, _, 5, _, 7, _, 9, _]
3. 3의 배수 제거: [2, 3, _, 5, _, 7, _, _, _]
4. 결과 소수: [2, 3, 5, 7]

def solution(numbers):
    # 1. 입력 숫자를 리스트로 변환하고, 최대값 계산
    digit = list(numbers)  # 입력 문자열을 리스트로 변환
    max_number = int("".join(sorted(digit, reverse=True)))  # 가능한 가장 큰 숫자 계산

    # 2. 에라토스테네스의 체로 소수 판별 배열 생성
    is_prime = [True] * (max_number + 1)  # 소수 여부 저장 (True: 소수)
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님
    for i in range(2, int(max_number**0.5) + 1):
        if is_prime[i]:  # i가 소수라면
            for j in range(i * i, max_number + 1, i):  # i의 배수는 소수가 아님
                is_prime[j] = False

    # 3. 모든 가능한 숫자 조합 생성
    unique_numbers = set()  # 중복 제거를 위한 set

    # 재귀적으로 숫자 조합 생성
    def generate_number(current, remaining):
        if current:  # current에 값이 있을 때만 추가
            unique_numbers.add(int(current))  # 생성된 숫자를 set에 추가
        for i in range(len(remaining)):  # remaining에서 숫자 하나 선택
            generate_number(current + remaining[i], remaining[:i] + remaining[i + 1:])

    generate_number("", digit)  # 조합 생성 시작

    # 4. 소수 개수 세기
    answer = 0
    for num in unique_numbers:
        if is_prime[num]:  # 조합된 숫자가 소수인지 확인
            answer += 1

    return answer  # 소수의 개수 반환

 

• 오늘의 공부 회고
  • 오랜만에 에라토스테네스의 체 사용해서 가물가물한 느낌쓰~
  • KEEP GOING~!