[프로그래머스] 소수 찾기 (level2) python

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3 

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

출처 : 프로그래머스

---

코드

from itertools import permutations
import math as m

def isPrime(n):
    if n<2:
        return False
    for i in range(2,int(m.sqrt(n))+1):
        if n%i == 0:
            return False
    return True
    
def solution(numbers):
    answer = 0
    numbs = [n for n in numbers]
    permu = [] # 순열리스트
    
    for i in range(1, len(numbs)+1):
        permu += list(permutations(numbs,i))
    
    permu1 = [int(''.join(p)) for p in permu]
    permu1 = list(set(permu1))

    for p in permu1:
        if isPrime(p):
            answer += 1
    return answer

 

풀이

소수판별은 에라토스테네스의 체 알고리즘으로 풀이했다.

 

하지만 이 문제에서는 numbers에 있는 문자열로 이루어질 수 있는 모든 숫자 조합이 소수인지 아닌지를 판별하는 것이 문제이다.

이를 해결하기 위해, 순열의 방법을 사용했다.

python 에서의 순열은 permutations이다.

 

길이가 0인 순열은 관련이 없으니, 1부터 numbers의 길이만큼 순열리스트를 만들었다.

또한, 순열 리스트에 있는 문자열을 숫자로 바꿔줬고, 중복을 제거하기 위해 set()을 적용하고 다시 list()로 바꾸었다.

 

이제 이 순열 리스트에 있는 것이 소수 판별 함수를 통해 소수를 판별했다.