[프로그래머스 코딩테스트 고득점 Kit / 완전탐색] 소수찾기 (python)

풀이 1 : 파이썬 재귀함수로 순열 직접 구현

import math

def solution(numbers):
    used = [0 for _ in range(len(numbers))]
    answer = set()

    def prime_perm(arr, n):
        if n > 0:
            num = int(''.join(arr))
            isPrime = True
            for i in range(2, math.trunc(math.sqrt(num)) + 1): # 소수인지 확인
                if num % i == 0:
                    isPrime = False
                    break
            if num != 0 and num != 1 and isPrime:
                answer.add(num)
                
            if n == len(numbers):
                return

        for index in range(len(numbers)): # 순열 만들기
            if not used[index]:
                used[index] = 1
                arr.append(numbers[index])
                prime_perm(arr, n+1)
                arr.pop()
                used[index] = 0
        
    prime_perm([], 0)

    return len(answer)

내 풀이

 

순열을 이용하여 문제 해결.

재귀함수로 순열 직접 구현하는데 애먹었다. 검색 찬스로 해결.

prime_perm(arr, n)는 answer 집합에 소수를 추가하는 함수이다. solution(numbers)안에 구현한 함수로, solution 함수 내에서 prime_perm([],0)을 실행하면 numbers 문자열에서 가능한 모든 소수의 조합이 나온다. 

n이 1보다 크면 arr을 int 형태로 만들어 소수인지 확인하고, 소수라면 answer 집합에 추가한다.

 

재귀함수를 다 돌면 answer에 만들 수 있는 모든 소수가 담겨지고, answer의 length를 리턴하면 답이 나온다.

 

재귀함수 동작 순서

예를 들어 numbers가 "1234"라고 하면

1. prime_perm([1], 1) : index == 1
2. prime_perm([1, 2], 2) : index == 2
3. prime_perm([1, 2, 3] , 3)
4. prime_perm([1, 2, 3, 4], 4) 에서 n(=4)이 len(numbers)랑 같으므로 return   ->   arr.pop() == 4
5. arr.pop() == 3
6. prime_perm([1, 2], 2)  : index == 3
7. prime_perm([1, 2, 4] , 3)
8. prime_perm([1, 2, 4, 3], 4) 에서 n(=4)이 len(numbers)랑 같으므로 return   ->   arr.pop() == 3
9. arr.pop() == 4
10. arr.pop() == 3
11. prime_perm([1], 1) : index == 2

계속 반복..

join 함수

num = int(''.join(arr))

리스트에 있는 요소를 합쳐서 하나의 문자열로 만들어주는 함수이다. 

arr = [1, 2, 3, 4, 5] 일 때, 

''.join(arr)    ->    "12345"

'-'.join(arr)   ->   "1-2-3-4-5"

의 결과 나온다.

 

풀이 2 : 파이썬 순열 내장함수 사용

from itertools import permutations
import math

def solution(numbers):
    answer = set()
    
    for i in range(1, len(numbers) + 1):
        
        arr = list(permutations(numbers, i))
        
        for j in arr:
            num = int(''.join(j))
            isPrime = True
        
            for k in range(2, math.trunc(math.sqrt(num)) + 1):
                if num % k == 0:
                    isPrime = False
                    break
            if num != 0 and num != 1 and isPrime:
                answer.add(num)
                

    return len(answer)

내 풀이

 

itertools의 permutations 함수를 사용.

permutations([1, 2, 3], 2)는 [1, 2, 3]에서 2개의 수를 뽑아 줄을 세울 수 있는 모든 경우를 의미한다. list로 반환하면 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] 리스트 안에 튜플 형식으로 반환된다.

 

반환된 결과를 각각 int 형태로 바꾼 뒤 소수인지 체크하고, 소수가 맞다면 answer 집합에 추가한다.그리고 answer의 length를 반환하여 결과를 출력한다.

 

 

실행 결과

(왼) 풀이1, (오) 풀이2

직접 구현하든 내장함수를 쓰든 별 차이 없는듯