[프로그래머스/Python] 소수 찾기 - Level2

 

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

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

import itertools
import math

# 소수인지 확인하는 함수
def sosu(n):
    if n <= 1: return False # 0과 1은 소수가 될 수 없음
    for i in range(2, int(math.sqrt(n))+1): # 에라토스테네스의 체에 의한 소수인지 확인
        if n % i == 0: return False
    return True

def solution(numbers):
    nums = list(numbers)
    answer = set() # 집합 생성
    
    for i in range(1, len(nums)+1):
        pm = list(map(''.join, itertools.permutations(nums, i))) # 순열을 사용하여 조합을 만듬
        for num in pm:
            if sosu(int(num)) == True: answer.add(int(num)) # 소수가 맞다면 집합에 값 저장

    return len(answer)

먼저 numbers의 한 문자씩을 가져와 조합해야하기 때문에 numbers를 한 문자씩 가져와 리스트로 nums에 저장하였습니다. answer은 리스트가 아닌 집합으로 정의하였습니다. 그 이유는 다음과 같은 결과 때문이었습니다.

 

 

리스트로 했을 때 중복된 값이 들어가서 실행한 결괏값과 기대값이 달랐습니다. 집합을 사용하면 중복이 제거되므로 중복을 사용했습니다.

숫자 조합의 최대 길이는 nums의 길이이므로 for문을 돌면서 nums길이까지 순열 조합을 하도록 했습니다. 숫자를 조합한 결과를 리스트로 만들어 pm에 저장합니다. 조합한 각 숫자가 소수인지 확인해야 하므로 for문을 통해 pm을 돌면서 소수인지 확인한 후 소수이면 answer에 저장했습니다. 

 

소수인지 확인하는 부분은 따로 빼서 다른 메소드에 정의하였습니다. 소수인지 확인하는 것은 에라토스테네스의 체에 의해 판별할 수 있습니다. 0과 1은 소수가 될 수 없으므로 바로 return False를 해주고 나머지 숫자는 for문을 돌면서 소수인지 확인합니다. 이 때 for문은 n의 제곱근까지만 도는데 그 이유는 예를 들어 n = 120인 경우 120 < 11^2 이므로 제곱근까지만 나눠보아도 소수인지 판별할 수가 있습니다. 어떠한 숫자로 나눠지는 순간 소수가 아니게 되므로 return False를 해주었고 for문에서 걸러지지 않은 숫자는 소수가 맞으므로 return True를 해줬습니다.

 

- 배운 점 -

① 집합(set)

집합은 중복을 허용하지 않으며 순서가 없는 자료구조입니다. 다음 예시를 보면 리스트와 집합의 차이를 직관적으로 이해할 수 있습니다.

my_list = ['A', 'B', 'C', 'D', 'B', 'D', 'E']
my_set = set(my_list) 
print(my_list) # 출력 = ['A', 'B', 'C', 'D', 'B', 'D', 'E']
print(my_set) # 출력 = {'D', 'E', 'A', 'B', 'C'}

 

② 순열(permutations)

순열은 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말합니다. 즉, 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수입니다. 따라서 순열에서는 (A,B) 와 (B,A)는 다른 것이 됩니다. 파이썬에서는 for문 없이 순열을 사용할 수 있도록 함수를 제공합니다.  순열을 사용하는 예시는 다음과 같습니다.

import itertools

arr = ['A', 'B', 'C']
nPr = itertools.permutations(arr, 2) # (조합할 요소가 담긴 리스트, 조합할 개수)
print(list(nPr))

# 출력 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

 

③ 에라토스테네스의 체

에라토스테네스의 체는 소수를 찾을 때 사용하는 원리입니다. 보통 소수를 찾을 때 이 원리를 주로 사용하는 것 같습니다. 이 원리는 해당 수보다 작은 모든 수로 나누어 보아서 소수인지를 판단하는 방법입니다. 다음 예시를 보면 좀 더 이해하기 쉬울 것입니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 5. 자기 자신을 제외한 3의 배수를 모두 지운다. 6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 7. 자기 자신을 제외한 5의 배수를 모두 지운다. 8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 9. 자기 자신을 제외한 7의 배수를 모두 지운다. 10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.