문제

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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의 크기 n만큼 반복문을 돌려서, numbers 중 1개, 2개 ... n개 뽑는 순열 조합을 구한다. = 1자리, 2자리 ... n자리수 만든다.
직접 구현해보려 했지만 시간 초과가 나서 결국 모듈을 사용했다ㅠ

💡 파이썬 itertools 모듈

• product(p,q, ..., [repeat=n]) : 데카르트 곱
• permutations(p, r) : p 중에서 r개를 뽑는 순열
• combinations(p, r) : p중에서 r개를 뽑는 조합
• combinations_with_replacement(p, r) : p중에서 r개를 뽑는 중복조합
  파이썬 API 문서 참고

주의할 점은, 이 함수들은 generator이다. 즉 루프를 돌며 한번 값을 던져주고 나면 그 값이 기억되지 않는다. 그렇기 때문에 이런 함수들을 쓰고 나서는 list() 등을 통해 iterator 객체에 값을 담아놔야 한다.
이 문제에서는 numbers에 같은 숫자가 들어있는 경우 중복 결과값이 나올 수도 있으니 set에 넣어서 중복을 제거해주면 되겠다.
(itertools 모듈과 generator 개념에 대해서는 나중에 다시 자세하게 포스팅해야겠다)

2)
set에 넣어놓은 숫자들을 대상으로 소수인지 아닌지 판별한다.
💎 n이 소수인지 판별할때는 1과 자신 외에 약수가 있는지 확인해보면 되는데, 약수를 구할때 n의 제곱근까지만 확인해보면 된다는 걸 이전 포스팅에서도 쓴 적이 있다. (프로그래머스-카펫 포스팅)

🌈 완성 코드

from itertools import permutations
import math

def solution(numbers): 
    result = set()
    for n in range(1, len(numbers)+1):
        for p in permutations(numbers, n):
            result.add(int(''.join(p)))
            # permutations는 generator 이기 때문에 루프 한번 돌고 결과값 사라짐
            # set에 담기
                            
    answer = 0
    for num in result:
        check = 0
        if num < 2:
            check = 1  # 1이면 소수 아님
        elif num == 2:
            pass   # 2이면 소수임
        else:     
            for i in range(2, int(math.sqrt(num))+1):            
                if num % i == 0:                
                    check = 1
                    break        
        if check == 0:            
            answer += 1

    return answer