[ 프로그래머스 / PYTHON ] 소수 찾기

문제 설명

소수 찾기

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

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

생각 방법

• 보자마자 순열, 에라토스테네스의 체를 사용해야 겠구나 생각.
• 문제에서 길이가 7이하인 문자열이라 했지만 10000000 개를 에라토스테네스의 체를 사용하는 것 보다 numbers의 조합에서가장 큰 수를 기준으로 해야겠다고 생각함.

1. 순열 라이브러리 불러오기
2. numbers를 한 개씩 자르고, 내림차순으로 정렬하여 number에 저장
3. number의 조합 중 가장 큰 수를 n 으로 설정
4. 에라토스테네스으 체 구현 (반복문 2번 돌면서 j를 i로 나누었을 때 나머지가0이면 소수가 아니면 False로
5. number의 개수만큼 돌면서 순열.
   6. 소수라면 answer에 추가
6. answer을 set()으로 바꾸어 중복 제거 후 return

코드

from itertools import permutations
def solution(numbers):
    answer = []
    number = [i for i in numbers]
    number = list(reversed(sorted(number)))

    n = int(''.join(number))
    pri = [True for i in range(n+1)]
    pri[0] = False
    pri[1] = False
    for i in range(2,(n+1)//2):
        for j in range(2*i,n+1,i):
            if j%i == 0:
                pri[j] = False

    for i in range(1,len(number)+1):
        for c in permutations(number,i):
            per = int(''.join(c))
            if pri[per]:    answer.append(per)

    return len(set(answer))