[프로그래머스] 소수 찾기 (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단계에서도 했었습니다. 그 코드를 이용해서 하겠습니다. 자릿수는 최대7까지 정해져 있기 때문에 입력받은 수의 길이만큼 소수를 찾아주는 함수에 전달합니다. (3자리면 10³을 입력으로 넣어주면 됩니다.) 이렇게 하면 입력받은 수의 자릿수에서 가질 수 있는 소수들을 모두 찾을 수 있습니다. 이제 입력받은 수를 조합하여 숫자를 만들어 주면 됩니다. 이것은 itertools에 있는 permutations를 사용합니다. 사용법은 아래서 설명하겠습니다. 소수, 조합된 수는 모두 집합 형태로 묶여있습니다. 이를 계산하여 소수인 수들의 집합을 찾고 크기를 구하면 됩니다.

​

나의 코드

from itertools import permutations
def search(n):
    n_list = set([num for num in range(3, n+1, 2)])
    for i in range(3, n+1, 2):
        if i in n_list:
            n_list -= set([i for i in range(i*2, n+1, i)])
    return n_list | set([2])

def solution(numbers):
    number_list = set([int("".join(item)) for i in range(7) for item in set(permutations(list(numbers), i + 1))])
    search_number_list = search(pow(10,len(numbers)))
    return len(number_list - (number_list - search_number_list))

permutations는 다음과 같이 사용합니다.

예를들어 num = [1,2,3,4] 라는 리스트가 있고, 이 리스트 내의 수들을 모두 조합하고 싶다면, 아래와 같이 사용하면 됩니다.

from itertools import permutations
num = [1,2,3,4]permutations(num,조합할 숫자 수)

조합할 숫자 수에 몇 개를 조합할건지 쓰시면 됩니다!