[알고리즘] 완전탐색 프로그래머스 2단계 - 소수 찾기

from itertools import permutations 

def solution(numbers):
    
    number_list = list(numbers)
    answer = []
    
    # 배열의 원소를 조합
    for i in range(len(number_list)):
        
        # 중복 제거
        set_list = set(list(map(''.join, permutations(number_list, i+1))))
        ori_list = list(set_list)
        
        # 소수 찾기
        for j in range(len(ori_list)):
            # 첫 글자가 '0'이면 포함 x
            if ori_list[j][0] != '0':   
                num = int(ori_list[j])  
                if num != 1:          
                    prime = []
                    for k in range(2, num):    
                        if num % k == 0:   
                            prime.append(k)
                            break
                    if len(prime) == 0:  
                        answer.append(num)

    return len(answer)

풀이과정

1. 입력받은 number string 값을 number_list 배열에 넣는다.
2. permutations 클래스는 배열의 각 원소를 조합하여 수열을 만들어준다.
3. 예를 들어 '0', '1', '1'은 '1'이 2개 있어 중복 값이 나오므로 set을 사용하여 중복값을 제거한 후 다시 list로 만들어준다.
4. 만들어진 문자열 중 첫 글자가 '0'이면 포함하지 않는다. 문자열을 int형으로 바꾼다.
5. 1은 소수가 아니므로 포함하지 않는다. 만약 어떤 수를 그 수보다 작은 수로 나눴을 때 나머지가 0이라면 소수가 아니다.
6. 아닌 값들을 anwer 배열에 넣은 후 정답을 구한다.

새로 배운 내용

순열

n개의 원소를 사용해서 순서를 정하여 r개의 배열로 나타내는 것

from itertools import permutations

num = [1,2,3]
permute = permutations(num, 2)

print(list(permute))

<output>
[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

itertools 모듈의 permutations 클래스를 사용한다.
permutations(배열, 갯수)은 배열의 원소를 갯수만큼 조합하여 tuple 형태로 만들어 준다.

조합

n개의 원소를 사용해서 순서의 관계없이 r개의 배열로 나타내는 것

from itertools import combinations

num = [1,2,3]
combi = combinations(num, 2)
    
print(list(combi))

<output>
[(1,2),(1,3),(2,3)]

itertools 모듈의 combinations 클래스를 사용한다.
permutations(배열, 갯수)은 배열의 원소를 갯수만큼 조합하여 tuple 형태로 만들어 준다.