Programmers 12977

explaination.md

실습 과제 1

2024-05-24

코드 설명

class PrimeChecker

소수를 판별하는 함수 is_prime(num: int) -> bool을 가진 클래스입니다. 에라토스테네스의 체를 사용하며, 소수 판별에 필요한 연산 결과와 값들을 내부적으로 저장합니다. 즉, 이 클래스는 똑같은 연산을 두 번 수행하지 않습니다.

    def is_prime(self, num):
        self.__expand_primes_until(num)
        return num in self.__primes

주어진 수 num이 소수인지 아닌지를 판별합니다. 작동 방식은 다음과 같습니다.

1. "아는 소수 목록"을 num까지 확장한다. (self.__expand_primes_until(num))
2. "아는 소수 목록" 안에 num이 있는지 확인한다.

    def __expand_primes_until(self, num):
        if num <= self.__check_size:
            return

        for i in range(self.__check_size, num + 1):
            if self.__check_prime(i):
                self.__add_prime(i)
            self.__check_size = i

"아는 소수 목록"을 주어진 수 num까지 확장합니다. 마지막으로 확인한 숫자로부터 num까지, 이 사이의 모든 정수가 소수인지 아닌지 체크하고 기록합니다. 확장할 필요가 없다면, 아무 일도 하지 않습니다.

    def __check_prime(self, num):
        if num <= 1: return False

        check_limit = floor(sqrt(num)) + 1
        for prime in self.__primes_list:
            if prime > check_limit:
                break
            if num % prime == 0:
                return False

        return True

"아는 소수 목록"에 있는 소수를 순회하며 나머지 연산을 수행, 받은 수가 소수인지 아닌지 판별합니다. "아는 소수 목록"에서 floor(sqrt(num)) + 1보다 큰 소수를 만나면, 종료합니다. 이 이후로는 계산을 더 할 필요가 없기 때문입니다.

def solution(nums):
    prime_checker = PrimeChecker()
    prime_count = 0

    for comb in combinations(nums, 3):
        challenge = sum(comb)
        if prime_checker.is_prime(challenge):
            prime_count += 1

    return prime_count

답안. itertools.combinations 함수를 이용해 받은 배열의 모든 조합을 구하고, 이 조합들에 대해, 각 조합의 총합을 각각 PrimeChecker을 이용하여 판별합니다.

solution.py

from itertools import combinations
from math import sqrt, floor

class PrimeChecker:
    def __init__(self):
        self.__primes = set()
        self.__primes_list = list()
        self.__check_size = 1

    def is_prime(self, num):
        self.__expand_primes_until(num)
        return num in self.__primes

    def __expand_primes_until(self, num):
        if num <= self.__check_size:
            return

        for i in range(self.__check_size, num + 1):
            if self.__check_prime(i):
                self.__add_prime(i)
            self.__check_size = i

    def __add_prime(self, num):
        if num in self.__primes:
            return

        self.__primes.add(num)
        self.__primes_list.append(num)

    def __check_prime(self, num):
        if num <= 1: return False

        check_limit = floor(sqrt(num)) + 1
        for prime in self.__primes_list:
            if prime > check_limit:
                break
            if num % prime == 0:
                return False

        return True


def solution(nums):
    prime_checker = PrimeChecker()
    prime_count = 0

    for comb in combinations(nums, 3):
        challenge = sum(comb)
        if prime_checker.is_prime(challenge):
            prime_count += 1

    return prime_count