[프로그래머스] 소수 찾기 [완전탐색] [python]

[프로그래머스] 소수 찾기 [완전탐색] [python] Level2

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

 

설계 및 구현

 

접근 방법

 

먼저 numbers의 모든 조합을 구한다

그후 조합의 수 중 소수를 추려낸후 중복제거 한뒤 갯수를 반환해주어 해결 할 수 있는 문제이다.

 

my_solution

from itertools import permutations

def isprime(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):
    answer = set()
    for i in range(len(numbers)):
        for j in list(permutations(numbers,i+1)):
            if isprime(int("".join(j))):
                answer.add(int("".join(j)))
    return len(answer)

1. 소수 판별 함수인 isprime()을 작성한다.

2. 중복 제거를 위해 answer을 set()자료형으로 선언해준다.

3. numbers의 길이까지 반복 i = 0 ~ len(numbers)-1까지

   그후 i+1을 permutations(numbers, i+1)을 통해 1~len(numbers)자리의 조합을 구한다.

   조합 중 숫자로 변환했을때 소수인 수를 answer에 저장한다.

4. answer에는 중복없이 numbers의 모든 조합의 소수가 들어 있다. answer의 길이를 반환해주면 문제 해결!