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

문제

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

프로그래머스

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

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

아이디어

일단 소수인지 아닌지 판별하는 함수를 구현한다. 

흩어진 숫자 조각을 이용해서 만들 수 있는 숫자를 모두 만든 이후 소수인지 아닌지 판별한다.

주어진 문자열을 0~9사이의 숫자로 쪼개고 가능한 모든 숫자열을 작성한다. 

숫자는 순서는 존재하지만 중복을 허용하지 않는 형태이므로 순열을 이용한다.

 

풀이

 

itertools에 순열이 구현되어 있어 import해서 사용했다.

permutations(문자 리스트, 숫자) 는 숫자 길이 만큼의 순열을 만들어 준다.

for문을 이용하여 문자열의 길이가 1에서 부터 numbers의 길이 만큼 가능한 순열을 만든다.

permutations의 출력이 튜플이기 때문에 join을 사용하여 붙여준다.

중복 제거를 위해 딕셔너리를 이용한 후 만들어진 숫자들이 소수인지 아닌지 판별한다.

from itertools import *

def solution(numbers):
    num = {}
    numbers = [i for i in numbers]
    for i in range(1,len(numbers)+1):
        aa = list(permutations(numbers,i))
        aa = [int(''.join(a)) for a in aa if a]
        for nn in aa:
            if nn not in num and nn != 0:
                num[nn] = 1
    number = list(num.keys())
    answer = 0
    for num in number:
        if is_prime(num):
            answer += 1
    return answer

def is_prime(num):
    if num == 1 :
        return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True