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

 

 

문제 링크

 

 

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

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

 

 

 

문제 설명

 

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때,

종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

 

제한 사항

 

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

 

입출력 예

 

"17"	3
"011"	2

 

입출력 예 설명

 

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

 

11과 011은 같은 숫자로 취급합니다.

 

 

문제 풀이

 

 

import math
from itertools import permutations

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


def solution(numbers):
    answer = []
    for i in range(1, len(numbers) + 1):
        arr = list(permutations(numbers, i))
        for j in range(len(arr)):
            num = int(''.join(map(str, arr[j])))
            if is_prime_number(num):
                answer.append(num)

    answer = list(set(answer))
    return len(answer)

 

 

어렵다..... 처음보는 개념들이 많이 나와서 정리를 해야겠다.

 

일단 문제 풀이의 개념을 설명하자면,

 

is_prime_number 함수는 소수를 판별해주는 함수이다.

숫자가 0 혹은 1일 경우 소수가 될 수 없으니 False를 반환함으로써 제외하고

그 외의 숫자들에 대해 판별을 하는데 for문의 범위를 math.sqrt 함수를 이용해

제곱근까지로 제한하는 이유는

제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 일어나게 되기 때문이다.

 

예를 들어 24의 약수들을 보면

1, 2, 3, 4, 6, 8, 12, 24가 있는데

24는 1*24, 2*12, 3*8, 4*6, 6*4, 8*3, 12*2, 24*1로 나타낼 수 있다.

이 때 24의 제곱근은 4. ... 으로 표현할 수 있다.

즉, 제곱근인 4를 기준으로 대칭이 나타난다.

대칭적으로 일어나는 부분은 중복이므로 2번 검사할 필요가 없기 때문에 제곱근 이전까지로 범위를 한정짓는 것이다.

 

 

이제 제곱근까지로 범위를 한정지었으니, 그 범위만큼 숫자를 더해가며

입력받은 n을 나눠보고 나누어떨어진다면 False를 반환(소수 X), 나누어떨어지지 않는다면 True(소수 O)를 반환한다.

 

 

solution 함수 안을 살펴보면,

 

가장 눈에 띄는 permutations 함수가 있다.

 

permutations 함수

 

permutations(반복 가능한 객체, 뽑을 숫자의 개수)

Permutations는 순열을 반환해주는 함수이다.

 

순열을 한 눈에 예를 들어 보면

 

permutations([1, 2, 3], 2)의 경우

(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)의 튜플의 형태로 반환하게 된다.

 

비슷한 형태로 combinations(조합) 함수도 존재하는데,

우리는 12, 21이 각각 다른, 즉 순서가 중요한 문제를 풀고 있으므로 permutations 순열 함수를 이용해야 한다.

(조합 함수는 순서가 달라도 같은 값들이 있으면 같은 것으로 친다)

 

permutations 함수를 사용하고 list로 둘러싸면 arr 배열에는

[(1, 2), (2, 3) ... ] 과 같은 형태로 저장된다.

 

이제 arr 배열에 저장된 값들을 하나씩 가져와서 소수 판별을 해주어야 하는데, 

위에 쓰여있듯 튜플 형태로 저장되어 있기 때문에 이를 정수 형태로 변형해주어야 한다.

 

이를 위해, int(''.join(map(str, arr[j])))의 형태로

튜플 하나를 string 형태로 매핑한 후 숫자 형태로 변형하는 방식을 이용한다.

 

소수 판별을 통해 True를 반환한 숫자를 answer 배열에 넣어준 후,

최종 결과를 제출할 때에는 set함수로 중복을 제거한 후 리스트의 길이를 나타낸다.

 

 

set 함수는 수학에서의 집합과 비슷한 개념으로 중복을 삭제해준다!

 

 

 

 

코드는 길지 않은데 처음 접하는 내용들이 많아서 풀이가 조금 길어졌다.

아래에는 프로그래머스상에 많은 사람들이 제출한 개념의 코드로 

에라토스테네스 체 라는 단어가 눈에 들어와서 나도 익혀보기 위해 가져왔다.

 

 

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)

 

코드가 정말 간결하다.

 

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로

마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.