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

소수 찾기

📌 문제

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

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

⚠️ 제한사항

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

📋 코드

from itertools import permutations

def prime_number():
    arr = [True] * 10000000
    arr[0], arr[1] = False, False

    for i in range(2, int(10000000 ** 0.5) + 1):
        if arr[i]:
            for j in range(2 * i, 10000000, i):
                arr[j] = False                

    return arr  

def solution(numbers):
    prime_arr = prime_number()

    result = set()
    for i in range(1, len(numbers) + 1):
        for perm in permutations(numbers, i):
            value = int("".join(perm))
            if prime_arr[value]:
                result.add(value)

    return len(result) 

💡 한마디

에라토스테네스의 체를 이용해서 풀었는데, 일반적으로 소수 구하듯이 푸는 게 더 빠를 것 같다.

코딩테스트 연습 - 소수 찾기