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

🗃️문제 설명

👉itertools 라이브러리를 사용하면 금방 풀 수 있겠지만 백트래킹으로 풀 수 있을 것 같다는 생각이 들어 백트래킹으로 문제를 해결

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

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

🖥️코드

import sys
sys.setrecursionlimit(10**6)

def solution(numbers):
    prime_set = set()
    numbers = list(map(int, numbers))
    visited = [False] * len(numbers)

	# 소수 판별 알고리즘
    def checking_prime(number):
        if number == 1 or number == 0:
            return False
        for i in range(2, (number // 2) + 1):
            if number % i == 0:
                return False
        return True
    
    # 백트래킹
    def backtracking(combination):
        if combination:
            num = int("".join(map(str, combination)))
            if checking_prime(num):
                prime_set.add(num)
        for i in range(len(numbers)):
            if not visited[i]:
                visited[i] = True
                combination.append(numbers[i])
                backtracking(combination)
                combination.pop()
                visited[i] = False
        
    backtracking([])
    return len(prime_set)

🔒문제 출처

프로그래머스 - 소수 찾기