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

링크 : 문제 바로가기

import math
import itertools

def is_prime_number(x):
    if x<=1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    result=[]
    numbers_list=list(numbers)
    numbers_len=len(numbers_list)
    for i in range(1,numbers_len+1):
        tmp_result=list(map(''.join, itertools.permutations(numbers_list,i)))
        result+=tmp_result
    result=list(map(int,result))    
    result=set(result)
    result=list(result)
    result.sort()
    
    for res in result:
        if is_prime_number(res)==True:
            answer+=1
    
    return answer

크게 numbers로 만들 수 있는 여러 숫자들을 구하는 함수, 각 경우의 숫자들이 소수인지 판별하는 함수로 나누어 코드를 작성했다.

• 소수 정의 : 1보다 큰 자연수 중 1과 자신만을 약수로 가지는 수
• is_prime_number 함수 : 처음에는 파라미터로 x라는 값을 받으면, 소수의 정의대로 2에서부터 x-1까지 모두 나누어 보면서 나뉘지 않을 경우 소수라는 판단을 내리려고 했다. 하지만 이렇게 모든 경우를 탐색할 경우 너무 비효율적이라는 판단을 해 코드를 수정했다. 파라미터로 x라는 값을 받았을 때, x의 제곱근보다 작거나 같은 정수 중 가장 큰 수를 찾았다. 이 수를 a라고 표현하여 설명해본다. a보다 큰 a+1로 x를 나누어 소수인지 아닌지를 판별한다고 했을 때, 필연적으로 x를 a+1로 나눈 몫은 a보다 작을 수 밖에 없다. ((a+1)^2 > x) 즉, a+1로 나눌 수 있으려면 a+1보다 작은 수로도 나눌 수 있어야 한다. 그럼 a+1까지 나누지 않아도 이미 a+1보다 작은 값들을 이용해 x를 나누며 a+1에 대한 점검도 가능하다는 뜻이다.
  • ex) 18이 소수인지 판별해라!
    –> 18의 제곱근보다 작거나 같은 정수 중 가장 큰 수 = 4
    –> 18을 4+1인 5로 나누면 나뉘지 않음(넘어감)
    –> 18을 4+2인 6으로 나누면 나뉘고 몫이 3이 나옴. 이 말은 18은 3으로도 나뉜다는 뜻.
    –> 즉!!! 4보다 큰 수로 나뉠 수 있다면 당연히 4보다 작은 수로도 나뉠 수 있어야함!
    –> 고로 2,3,4까지만 나누어보면 5,6,7… 로 나누지 않아도 소수 판별이 가능함
• solution 함수 : itertools 라이브러리의 permutations 함수를 이용했다. 이를 통해 numbers로 가능한 순열들을 구할 수 있다. 이때, 중복된 값들이 발생할 수 있다. 예를 들어 1이 2개 있다면 첫번째1 두번째1, 두번째1 첫번째1 은 결국 같은 값을 의미하므로 빼줘야 했다. 이런 중복을 set을 이용해 해결했다. 또 solution 함수 내에서 is_prime_numer 함수를 호출해 numbers 조합들을 파라미터값으로 넣고 소수면 answer 변수에 1을 더하도록 했다.

알고리즘 : 완전탐색