[프로그래머스 | 2단계] 소수찾기(백트랙킹)

문제 설명

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

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

제한사항

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

입출력 예numbersreturn

"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

풀이

def DFS(num, L, result, visit) : 
    answer =[]
    if len(result) != 0:
        answer.append(int("".join(result)))
    if L == len(num) :
        return answer
    else :
        for i in range(len(num)) :
            if visit[i] == 0 :
                visit[i] = 1
                result.append(num[i])
                for n in DFS(num, L+1, result, visit):
                    if n not in answer:
                        answer.append(n)
                result.pop()
                visit[i] = 0
    return answer

#소수 판별
def isPrime(n) :
    for i in range(2, n) :
        if n % i == 0 :         #나누어 떨어지는 수가 있으면 소수가 아니다.
            return False
    return True

def solution(numbers):
    result = []
    num_list = []
    visit = [0] * len(numbers)
    for i in numbers :
        num_list.append(i)
    answer = 0
    nums = DFS(num_list, 0, result, visit)

    for n in nums :
        if n > 1 and isPrime(n) :
            answer += 1
    return answer