[프로그래머스] 소수 찾기 - 파이썬(python)

 

나의 풀이

from itertools import permutations

def solution(numbers):
    answer = []
    s = []
    for i in range(1,len(numbers)+1):
        s += (list(map(''.join, permutations(numbers, i))))
        
    s = list(map(int, s))
    s = list(set(s))
    print(s)

    for i in s :
        if i < 2 : continue
        elif i == 2 : 
            answer.append(i)
            continue
        for j in range(2, int(i**0.5) + 1) :
            if int(i) % j == 0 :
                break
            elif j == int(i**0.5) :
                answer.append(i)


    return (len(answer))

• 흩어진 종이 조각의 개수 n에 따라, 1~n까지 각 자리수의 문자열을 permuations 을 통해 만들었다.
• -> s += (list(map(''.join, permutations(numbers, i))))
• 그런다음, map 을 이용해 모든 문자열을 int 로 변경하였고, 중복을 없애기 위해 set 을 씌워주었다.
• 반복문을 돌면서 각 숫자가 소수인지 판별하였다.
• 0,1 의 경우에는 소수가 아니며, 2의 경우 소수임을 조건문을 통해 직접 명시하였다.
• 2~ 해당 숫자의 제곱근까지 확인하며, 그 숫자로 나눠진다면 소수가 아니라고 판별하였다.

 

itertools.permutations(iterable, r=None)은 반복 가능 객체 중에서 r개를 선택한 순열을 반환하는 함수이다.

 

 

다른 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

코드의 논리는 나와 비슷하지만, 더욱 깔끔하게 작성한 풀이이다.

• a라는 set() 집합하나를 생성한다.
• 문자열 n을 list화 한 것에서 각 자리수만큼의 순열을 생성하고 이를 a와 합집합 연산을 한다. 
• 그런다음, 차집합 연산을 통해 집합에서 0,1의 원소를 제거한다. 
• 그런다음, 에라토스테네스 체 의 원리를 이용하여 소수가 아닌 것들을 집합에서 제거한다.
• 2부터 a에서 가장 큰숫자의 제곱근까지 돌면서, 해당 숫자들의 배수를 a집합에서 차집합으로 제거한다.

 

<set 집합 연산자>

| - 합집합 연산자
& : 교집합 연산자
- : 차집합 연산자
^ : 대칭차집합 연산자(합집합 - 교집합)
|=, &=, -=, ^= : = 과 조합함으로써 연산과 동시에 할당