[프로그래머스] Lv2. 소수 찾기 파이썬 / 분류 : 완전 탐색

소수 찾기

문제 설명

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

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

제한사항

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

입출력 예numbersreturn

"17"	3
"011"	2

내 풀이

import math
from itertools import permutations

def solution(numbers):
    answer = []
    num_list = list(numbers)
    nums = []
    for i in range(1, len(numbers)+1):
        temp = permutations(num_list, i)
        for t in temp:
            nums.append(''.join(t))
    for num in nums:
        if isPrime(num):
            answer.append(int(num))
    return len(set(answer))

def isPrime(n):
    n = int(n)
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

• list()로 문자로 주어진 숫자를 배열에 한자리씩 들어가도록 만들기
• 1부터 문자의 길이를 for문으로 돌면서 permutations()를 이용해 각 길이의 숫자 순열조합 만들기
• permutation()은 결과를 튜플로 반환해서 for문을 이용해 nums배열에 각 숫자를 저장
• for문을 이용해 nums 배열을 돌면서 isPrime()으로 소수인지 판별하고 answer 배열에 저장
• 예제의 '011'의 경우에 동일한 숫자가 여러개 만들어질 수 있어서 answer 배열을 집합으로 만들어 중복 제거하고 길이를 리턴

다른 사람 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

• permutations 함수를 사용하여 입력된 숫자 n의 순열을 생성. 생성된 순열을 각각 정수로 변환하여 집합 a에 추가
• 집합 a에서 0과 1을 제거하고 에라토스테네스의 체 알고리즘을 사용하여  2부터 a의 최댓값의 제곱근까지의 수를 반복하면서, 해당 수의 배수를 모두 집합 a에서 제거.
• 마지막으로 집합 a의 길이를 반환하여 소수의 개수를 계산
• |= 연산자는 병합 연산자로, 이미 값이 있는건 안넣고, 없으면 넣는 것이다.