[프로그래머스] 소수 찾기 - python

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

프로그래머스

 

문제 유형 : 완전탐색

난이도 : level 2

 

코드

내 코드

import itertools 

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def remove_non_primes(arr):
    return [num for num in arr if is_prime(num)]

def solution(numbers):
    arr = []
    for i in range(1, len(numbers)+1):
        arr.extend(list(itertools.permutations(numbers, i)))
    
    li = set()
    for i in arr:
        _str = ''.join(i)
        li.add(int(_str))
    
    li = remove_non_primes(li)
    
    return len(li)

• permutations 사용해서 모든 경우의 수 arr에 저장
• 숫자로 변환 후 같은 숫자 삭제 (set 사용)
• remove_non_primes() 함수 사용해서 소수가 아니면 삭제
• is_prime() 함수 사용해서 소수 인지 아닌지 판별

 

다른 풀이

import math
def check_prime(n):
    if n < 2:
        return False

    if n == 2:
        return True

    for i in range(2, int(math.sqrt(n)) + 1):
        if (n % i) == 0:
            return False

    return True

number_set = set()
def permutation(base, array):
    if base:
        number_set.add(int(base))

    for i, s in enumerate(array):
        permutation(base + s, array[:i] + array[i+1:])

def solution(numbers):
    answer = 0

    permutation("", list(numbers))

    answer = len(list(filter(check_prime, number_set)))

    return answer

내 풀이랑 비슷하긴 한데 이런 방법도 있군

• python filter : https://www.daleseo.com/python-filter/