[프로그래머스 lv.2] 소수 찾기 (파이썬)

문제

링크

문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.

풀이

1. 숫자 중 가장 큰 수를 찾고 numbers와 길이가 같은 숫자를 만든다(chkN)
2. 그 숫자까지 소수인 수를 표시하는 리스트를 만든다(primeList)
3. 만들어 질 수 있는 소수를 모두 set()에 추가한다
4. set()은 중복을 없애주므로 그 길이를 구한다

코드

from itertools import permutations as pm

def solution(numbers):
    N = len(numbers)
    
    # 소수 리스트 만들기
    M = max(numbers, key=lambda x:int(x))
    chkN = int(N*M)+1
    primeList = [1] * chkN
    primeList[0] = primeList[1] = 0
    for i in range(2, chkN//2 + 1):
        for j in range(i*2, chkN, i):
            primeList[j] = 0

    # 소수인지 확인
    ans = set()
    for cnt in range(1, N+1):
        for num in pm(numbers, cnt):
            num = int(''.join(list(num)))
            if primeList[num]:
                ans.add(num)
    return len(ans)