[프로그래머스/파이썬] 소수 찾기

 

 

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

프로그래머스

 

완전탐색 문제

 

순열 (permutation)

몇 개를 골라 순서를 고려해 나열한 경우의 수

순서를 고려하므로 (A, B)와 (B, A)는 다르다

 

조합 (combination)

몇 개를 골라 순서를 고려하지 않고 나열한 경우의 수

순서를 고려하므로 (A, B)와 (B, A)는 같다

 

 

💫 정답 코드

from itertools import combinations, permutations
def solution(numbers):
    num = []
    combi = []
    for i in range(1, len(numbers)+1):
        combi.append(list(permutations(numbers, i)))
        
    for i in combi:
        for j in range(len(i)):
            num.append(int(''.join(i[j])))
    
    num = set(num)
    answer = len(num)
    for i in num:
        if i == 0 or i == 1:
            answer -= 1
        else:
            for j in range(2, i):
                if i % j == 0:  
                    answer -= 1
                    break
    return answer

 

 

👩‍💻코드 풀이

 

1️⃣

순열을 만들기 위해 import해준다

from itertools import combinations, permutations

 

 

2️⃣

문제를 보자마자 numbers를 하나하나 잘라서 이를 토대로 순열을 만들었다.

예를 들어 "17"이라면 "1", "7"로 나누어서 [[('1',), ('7',)], [('1', '7'), ('7', '1')]] 형태로 만든다.

    for i in range(1, len(numbers)+1):
        combi.append(list(permutations(numbers, i)))

 

 

3️⃣

다음 형식으로 뜨는 튜플형을 [1, 7, 17, 71]으로 변경시켜준다. 또한, 중복되는 수를 제거해준다

    for i in combi:
        for j in range(len(i)):
            num.append(int(''.join(i[j])))
    num = set(num)

 

 

4️⃣

최종적인 답을 도출하기 위해서 현재 [1,7,17,71] 갯수에서 소수가 아닌 것을 제거하는 형식으로 한다

우선 0, 1은 소수가 될 수 없기 때문에 그럴 경우에는 제거해준다

그 외에는 1과 자신을 제외한 수를 나눠보고 나누어떨어진다면 소수가 아니므로 제거해준다.

answer = len(num)
    for i in num:
        if i == 0 or i == 1:
            answer -= 1
        else:
            for j in range(2, i):
                if i % j == 0:  
                    answer -= 1
                    break

 

 

5️⃣

최종 값을 출력해준다

    return answer