[완전 탐색] 소수 찾기

yejichoi·2023년 7월 21일

알고리즘 스터디

목록 보기

73/153

소수 찾기

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

🌿 풀이

정석은 dfs 로 푸는거지만 permutaions(순열)도 가능

from itertools import permutations
import math

def is_prime(x):    #소수 판별 함수
    for i in range(2, int(x**0.5)+1): 
    # 제곱근 구하기 , 소수 시작은 2
        if x % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    n = list(numbers)

    a = []
    for i in range(1, len(n)+1):
        a += list(permutations(n, i))   #경우의 수 반환

    b = []
    for i in a:
        b.append(int(''.join(i)))   
    b = list(set(b))    #경우의 수를 int형으로 담은 배열 b 선언

    for i in b:
        if i <= 1:
            continue    #1 이하면 무시
        elif is_prime(i):   # 소수면
            answer += 1     # answer 증가

    return answer

#dfs 
def chk_prime(number):
    if number == 0 or number == 1:
        return False
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

def search_numbers(numbers, i, chk_nums, prime_list):
    for j in numbers:
        num = i + j
        rem = numbers.replace(j, '', 1)
        if int(num) not in chk_nums:
            chk_nums.append(int(num))
            if chk_prime(int(num)):
                prime_list.append(int(num))
        if rem:
            search_numbers(rem, num, chk_nums, prime_list)

def solution(numbers):
    chk_nums = []
    prime_list = []
    answer = 0
    for i in numbers:
        if int(i) not in chk_nums:
            chk_nums.append(int(i))
            if chk_prime(int(i)):
                prime_list.append(int(i))
        rem = numbers.replace(i, '', 1)
        search_numbers(rem, i, chk_nums, prime_list)
    answer = len(prime_list)
    return answer