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

chanyeong kim·2021년 12월 16일

완전탐색 프로그래머스

프로그래머스

목록 보기

32/51

📩 -->문제설명

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

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

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

💡 solution(사용언어: python)

from itertools import permutations
# 조합을 이용해서 만들 수 있는 수를 만들어준다.
def solution(numbers):
    prime=[]
    for i in range(1,len(numbers)+1):
        for j in list(set(permutations(numbers, i))):
            if ''.join(j)[0]!='0':
                prime.append(int(''.join(j)))
    # 소수를 answer에 담아준다.
    answer=[]
    for i in prime:
        if i<2:
            continue
        check = True
        for j in range(2, int(i**0.5)+1):
            if i%j==0:
                check=False
                break
        if check:
            answer.append(i)
    return len(set(answer))

👉 설명

먼저 numbers에 있는 수들을 이용해서 만들 수 있는 수를 '조합'을 이용해서 만들어 준다.
효율성 때문에 통과 못할 것 같았는데, 완전탐색이라 그런지 통과했다...(0으로 시작하거나 중복인 애들은 빼주었다.)
소수인지 확인하는 방법은 '에라토스테네스의 체'를 이용했는데 설명은 다음과 같다.
- i를 2부터 해당 숫자의 제곱근까지(i**0.5)로 나누어 주었을 때 모두 나누어 떨어지지 않으면 소수이다.
이부분에서 은근 애를 먹었는데, 결국은 check가 True 일때만(소수인 경우) answer에 담아 주었다.

다른 풀이

primeSet = set()


def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False

    return True


def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])


def solution(numbers):
    makeCombinations("", numbers)

    answer = len(primeSet)

    return answer