[프로그래머스/Programmers] 소수 찾기 _2- Python

Link

코딩테스트 연습 - 소수 찾기

 

Solution

해당 문제는 permutations를 알고있다면 쉽게 해결할 수 있는 문제였고 에라토스테네스의 체의 개념을 알고 있었다면 시간을 줄이는데 많은 도움이 됐을 것이다.

해당 블로그에서 소수 찾기_1 문제의 글을 보면 기본적인 개념을 알 수 있을 것이다.

또한 permutations()와 함께 combinations()와 product()까지 함께 알아두면 좋기에 자세한 설명은 아래쪽에 첨부하니 참고하기 바란다.

Other Solution의 풀이는 permutations()를 사용하지 않았지만 재귀함수를 사용하여 해결한 멋진 풀이라 생각해 첨부하니 감상하고 지나가면 좋을것 같다.

from itertools import permutations

def is_prime(n):
    if n == 0 or n == 1:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True

def solution(numbers):
    answer = []

    for i in range(1, len(numbers) + 1):
        nums = list(permutations(numbers, i))

        for j in range(len(nums)):
            if is_prime(int(''.join(nums[j]))):
                answer.append(int(''.join(nums[j])))

    answer = set(answer)

    return len(answer)

🔑 key point: itertools.permutations()
📌 Tip: 에라토스테네스의 체

 

Other Solution

primeSet = set()


def isPrime(number):
    if number in (0, 1):
        return False

    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            return False

    return True


def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])


def solution(numbers):
    makeCombinations("", numbers)

    answer = len(primeSet)

    return answer

🔑 key point: Recursive Function

첨부

https://docs.python.org/ko/3/library/itertools.html#itertools.product

https://velog.io/@davkim1030/Python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-product-itertools