[프로그래머스] 완전 탐색 - 소수 찾기

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

코딩테스트 연습 - 소수 찾기

---

[사용한 함수]

- permutations : 순열을 구하는 함수

from itertools import permutations

permutations(iterable, r=None): r개로 이루어진 순열 반환하는 함수

                                          r에 None이나 빈칸으로 두면 iterable의 길이의 순열 생성

 

ex. arr = ['A', 'B', 'C']

    print(list(map(''.join, permutations(arr, 2))))

    결과 :  ['AB', 'AC', 'BA', 'BC', 'CA', 'CB'] 

 

---

[풀이 과정]

1. 주어진 numbers에서 나올 수 있는 순열의 길이는 1부터 len(numbers)까지 가능하기 때문에 반복문을 돌리면서 순열을 리스트로 만들어준다.

 

2. 중복된 값을 제외하기 위해 set함수로 만들어진 리스트를 묶어주고 각 값이 소수인지 check함수를 사용해 확인한다.

 

3. check함수

- 소수인지 확인하려는 값(val)이 1보다 작거나 같으면 소수가 아니므로 -1을 반환한다.

- 1보다 큰 값이라면 2부터 val-1까지 값으로 나누어 떨어지는지 확인한다.

   - 만약 나누어 떨어지면 소수가 아니므로 -1을 반환한다.

   - 나누어 떨어지는 수가 없다면 소수이므로 1을 반환한다.

 

4. check함수의 결과가 1이면 answer리스트에 추가한다.

 

5. answer에 겹치는 값이 있을수도 있으므로 len(set(answer))을 반환한다.

---

[소스 코드]

from itertools import permutations

def check(val):
    if val <= 1:
        return -1
    for n in range(2, val):
        if val % n == 0:
            return -1
    return 1

def solution(numbers):
    answer = []
    
    for i in range(len(numbers)):
        arr = list(map(int, map(''.join, permutations(numbers, i+1))))
        
        for j in set(arr):
            res = check(j)
            if res == 1:
                answer.append(j)
                
    return len(set(answer))