[프로그래머스 Lv.2] 소수 찾기 (완전 탐색) @

문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

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

 

코드 

from itertools import permutations

def solution(numbers):
    answer = 0
    size = 10000000
    
    # 1. 처음부터 모든 숫자에 대해 소수 판별 후 배열에 저장
    arr = [1] * size
    arr[0] = arr[1] = 0
    
    for i in range(2,int(size**0.5)):
        if arr[i] == 1:
            for j in range(i*i,size,i):
                arr[j] = 0
                
    # 2. 길이 1, 2, 3 .. 길이의 문자열을 만들며 소수 개수 계산
    numbers = list(numbers)
    for i in range(1, len(numbers)+1):
        for p in permutations(numbers, i):
            num = int("".join(p))
            if arr[num] == 1:
                answer += 1
                arr[num] = 0
    
    return answer

 

풀이 참고

from itertools import permutations

def solution(numbers):
    answer = set()
    
    # 1. 만들 수 있는 숫자 문자열 조합을 set형 answer 변수에 저장
    for i in range(1, len(numbers)+1):
        perms = permutations(list(numbers),i)
        perms = map("".join, perms)
        answer |= set(map(int, perms))
    
    # 2. answer에서 소수가 아닌 숫자들을 삭제
    answer -= set((0, 1))
    
    for i in range(2, int(max(answer) ** 0.5) + 1):
        not_prime = range(i*i, max(answer) + 1, i)
        answer -= set(not_prime)
    
    return len(answer)

 

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