[python] 프로그래머스: 소수 찾기

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

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

 

구현해야 할 것들

1. 소수 판별하는 함수 (is_prime)

2. 주어진 문자열의 요소들로 만들 수 있는 모든 숫자열을 구하기 (combination)

3. 가능한 소수의 경우의 수를 셈하기 (set)

 

 

code

from itertools import permutations

def is_prime(num):
    if num == 1 or num == 0:
        return False
    else:
        n = int(num ** 0.5)

        for i in range(2, n + 1):
            if num % i == 0:
                return False
        return True


def solution(numbers):
    length = len(numbers)
    ans = set()
    for i in range(1, length + 1):
        p = list(permutations(numbers, i))
        for v in p:
            if v[0] == '0':
                continue
            number = int(''.join(v))
            if is_prime(number):
                ans.add(number)
    print(len(ans))

 

문자열이 "123" 이 주어지면, 이 숫자카드들로 가능한 조합을 모두 구해야 소수의 갯수 또한 구할 수 있으므로

먼저 permutation(iterable,갯수) 함수로 순열의 list 를  순열길이 1~number 만큼 반본적으로 구한다.

 

이후 구해진 순열 1개마다, is_prime 함수를 통해 소수인지를 판단한다.

 

* 이 때, 011, 00123 등, 맨 앞자리가 0인 경우엔 어차피 011 -> i가 2일때, 11 등으로 이전의 경우에 소수인지를 판별 했으므로 소수 판별에서 제외한다. 

 

* 구해진 순열 v 는 ['1','2','3] 의 형태이므로, 이를 하나의 숫자열로 concatenation 하기 위해 str.join(iterable) 함수를 사용해 문자열로 만든뒤, 이를 int() 로 정수 형태 숫자열로 치환한다.

 

이렇게 하면 반복적으로 같은 숫자열을 검사하게 되는데, 이때 count += 1과 같은 형태로 답을 구하게 되면, 중복된 소수에 대해서도 값이 증가해 결과가 다르게 된다.

 

이를 방지하기 위해 set() 을 통해 중복된 소수에 대해서는 합산하지 않게 하였다.