완전탐색 - 소수찾기 (Lv.2)

from itertools import permutations
import math
def solution(numbers):
    answer = 0; numList = list(numbers); candiSet = set()
    for i in range(len(numList)):
        permuNumList = list(permutations(numList, i+1))
        for eachSet in permuNumList:
            num = int(''.join(eachSet))
            chk = True
            if num in [0,1]:
                chk = False
            for i in range(2, int(math.sqrt(num))+1):
                if num%i == 0:
                    chk = False
                    break
            if chk == True:
                candiSet.add(num)
            
    return len(candiSet)

문제 설명

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

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

 

<My Source Code 1>

from itertools import permutations
def solution(numbers):
    answer = 0; numList = list(numbers); candiSet = set()
    for i in range(len(numList)):
        permuNumList = list(permutations(numList, i+1))
        
        for eachSet in permuNumList:
            candiSet.add(int(''.join(eachSet)))
        
    for i in candiSet:
        if ((i!=1) and (i!=0)) and ((i%2!=0) and (i%3!=0) and (i%5!=0)):
            answer+=1
    return answer

permutations 메소드를 이용해 numbers를 이용한 순열을 구해서, 중복을 없앤 후(set), 2, 3, 5로 나누어지지 않고, 1또는 0이 아닌 수로 소수를 찾는 방법으로 풀이하였다. 

 

하지만 2개빼고 테스트케이스 에러가 발생했다... ㅠ.ㅠ

 

<My Source Code 2>

if (i not in [0,1]) and ((i in [2, 3, 5, 7]) or ((i%2!=0) and (i%3!=0) and (i%5!=0) and (i%7!=0))):

일단 첫번째 코드에서 내가 범한 실수는 아래와 같은 조건을 뺐다는 것이다.

- 0, 1은 실수가 아니다.

- 2, 3, 5, 7은 실수다.

- 2, 3, 5, 7로 나누어지지 않는 수가 실수다.

 

하지만 이렇게 바꾸었더니 절반은 맞고, 절반은 틀렸다.

내가 만든 가설(=실수의 조건)이 틀렸을 확률이 높아보인다.

 

<My Source Code 3>

from itertools import permutations
import math
def solution(numbers):
    answer = 0; numList = list(numbers); candiSet = set()
    for i in range(len(numList)):
        permuNumList = list(permutations(numList, i+1))
        for eachSet in permuNumList:
            num = int(''.join(eachSet)); chk = True
            # 0과 1은 소수가 아니므로 제외
            if num in [0,1]:
                chk = False
            # 0,1 이외의 수로 나누어지면 = 약수가 존재하면 = 소수X
            for i in range(2, int(math.sqrt(num))+1):
                if num%i == 0:
                    chk = False
                    break
            if chk == True:
                candiSet.add(num)
            
    return len(candiSet)

그래서 결국 약수를 구하는 식으로 대체해 약수를 구할 수 있으면 소수가 아니므로 이를 이용해 소수의 개수를 구하는 알고리즘을 짰다.