[프로그래머스/Python] 소수 찾기

문제 정보

제목 : 소수 찾기

난이도 : Lv.2

사용 언어 : Python

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

문제 설명

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

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

---

나의 풀이

순열과 조합을 구할 수 있는 itertools 모듈을 사용했습니다. 둘 중 순열을 사용하여 문제를 해결했습니다. 1부터 numbers+1만큼 반복하는 for문을 생성합니다. 내부의 for문을 이용해 i개만큼 numbers에서 선택하여 순열을 만듭니다. 만들어진 리스트를 join()함수를 통해 numSet에 int형으로 변환하여 저장합니다. 모든 경우의 수를 구했다면 for문을 이용하여 numSet에 하나씩 접근한 후 직접 정의한 is_prime()함수를 이용하여 소수인지 판별합니다. 소수라면 answer을 +1 합니다. 반복이 끝나면 answer을 리턴해줍니다.

 

코드

from itertools import permutations

def is_prime(n):
    if ( n < 2 ) :
        return False
    else :
        for i in range(2,int(n**(1/2))+1) :
            if ( n % i == 0) :
                return False
    return True

def solution(numbers):
    answer = 0
    numSet = set()
    for i in range(1,len(numbers)+1) :
        for j in list(permutations(numbers,i)):
            numSet.add(int(''.join(j)))
            
    for n in numSet :
        if( is_prime(n) ) :
            answer += 1
    return answer