소수 찾기(완전 탐색)

🔗 문제 링크

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

❔ 문제 설명

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

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

⚠️ 제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

💡 풀이 (언어 : Python)

시간 복잡도 오래 걸릴 것 같은데... 풀 수 있을까? 했지만 해결했다. permutations로 문자열로 만들 수 있는 모든 경우의 수를 join과 int로 숫자로 만들고 소수를 체크하는 함수를 정의하고 이걸로 소수로 판별되면 set에 넣어주는 알고리즘이다.

from itertools import permutations
# n이 소수면 True
def check(n):
    if n < 2:
        return False
    # 2로 나누어지는 약수까지만 체크하면 됨    
    for i in range(2, n//2 + 1):
        if n % i == 0:
            return False
    return True
        
def solution(numbers):
    # 중복 수를 제거하기 위한 set
    numSet = set()
    for i in range(1, len(numbers)+1):
        # 1자리, 2자리 .... 자리 수 케이스
        caseList = list(permutations(numbers, i))
        for j in range(len(caseList)):
            candidate = int("".join(caseList[j]))
            # 소수면 set에 넣어줌
            if check(candidate):
                numSet.add(candidate)
                
    return len(numSet)