문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

접근 방법

이번 문제는 numbers를 리스트로 변경하여 모든 조합의 경우를 따로 저장하고 이 조합을 순회하면서 조합된 순으로 수를 만들어 이 수가 소수인지 판별하는 방식으로 접근하였다.

처음 시도에는 소수인지 판별하는 함수에서 for문의 범위를 1~n+1로 두고 나누어 떨어지는 경우가 2일 경우에 소수라고 판별하도록 작성하였고 이로 인해서 시간 초과가 발생하였다.

소수 판별 함수의 시간을 줄일 수 있는 방법으로 for문의 범위를 2~sqrt(n)+1로 두고 나누어 떨어지는 경우가 발생하면 바로 소수가 아니라고 판별하는 방법을 찾을 수 있었다. 16을 예로 들면 2,3,4만 나누어 보아도 소수가 아니라는 것을 바로 알 수 있다.

소수 판별 함수의 수행 시간을 줄여 해결하였다.

• 소수 판별 함수 is_prime을 n을 인자로 갖도록 선언한다.
  -> 만약 n이 1보다 작거나 같다면 False를 반환한다.
  -> 2부터 sqrt(n)+1까지 반복하는 i에 대한 for문을 돌린다.
  --> 만약 n이 i로 나눠떨어진다면 False를 반환한다.
  -> for문을 끝까지 정상수행 하고 나오면 True를 반환한다.
• 정답을 저장하는 변수 answer를 0으로 선언한다.
• numbers를 리스트로 바꿔 n_list에 저장한다.
• n_list의 조합을 저장할 배열 per을 선언한다.
• 조합을 생성하기 위해 사용할 변수 cur을 0으로 정의한다.
• cur이 numbers의 길이보다 작을 동안 반복하는 while문을 돌린다.
  -> cur을 1 증가시킨다.
  -> per에 n_list를 cur개로 조합을 생성하여 더한다.
• 조합으로 만든 숫자의 중복을 체크할 배열 nums를 선언한다.
• per의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> 임시 변수 tmp에 per[i]를 문자열로 바꾼 것을 int형으로 저장한다.
  -> tmp가 nums에 없을 경우,
  --> nums에 tmp를 넣어준다.
  --> 만약 is_prime(tmp)가 True일 경우 answer를 1 증가시킨다.
  -> tmp가 nums에 있을 경우, 다음으로 넘어간다.
• answer를 반환한다.

solution.py

from itertools import permutations
import math
def solution(numbers):
    def is_prime(n):
        if n<=1:
            return False
        for i in range(2, int(math.sqrt(n))+1):
            if n%i==0:
                return False
        return True
    answer = 0
    n_list = list(numbers)
    per=[]
    cur=0
    while cur<len(numbers):
        cur+=1
        per+=list(permutations(n_list, cur))
    nums=[]
    for i in range(len(per)):
        tmp=int(''.join(per[i]))
        if tmp not in nums:
            nums.append(tmp)
            if is_prime(tmp):
                answer+=1
        else:
            continue
    return answer