[프로그래머스 lv1] 소수 만들기 (파이썬)

Summer/Winter Coding(~2018) 의 소수 만들기 문제이다.

 

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

 

 

 

 

 

 

입출력 예 설명

입출력 예 #1
    [1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2
    [1,2,4]를 이용해서 7을 만들 수 있습니다.
    [1,4,6]을 이용해서 11을 만들 수 있습니다.
    [2,4,7]을 이용해서 13을 만들 수 있습니다.
    [4,6,7]을 이용해서 17을 만들 수 있습니다.

 

---

나의 풀이

이 문제의 포인트는 소수를 판별하는 것과 리스트에서 3개의 숫자를 조합하는 것이다.

1. 리스트에서 숫자 조합

우선 리스트에서 3개의 숫자를 조합하는 것은 라이브러리로 간단하게 해결했다.

from itertools import combinations

nums = [1, 2, 3, 4, 6, 7, 9, 10]
combi = list(combinations(nums, 3))
print(combi)

itertools의 combinations 라이브러리를 import하고

combinations(리스트, 묶을 숫자 개수) 를 수행하면 리스트에서 묶을 숫자 개수만큼 조합된다.

물론 리스트 외에 튜플 등의 순회가능한 자료구조를 사용할 수 있다.

combinations에서 나온 결과를 list()에 넣거나 tuple()에 넣는 등의 작업으로 수행할 수 있다. 

리스트에서 숫자 3개씩 중복없이 묶은 결과이다.

from itertools import combinations
nums = [1, 3, 4, ... , 10] # 정렬되지 않아도 됨
combi = list(combinations(nums, 3)) # 조합된 목록을 리스트로 combi에 저장

for case in combi:
	# 작업 내용
    pass

for ~ in 문을 사용하면 각 조합된 경우를 순회하며 작업할 수 있다.

이 문제에서는 3개 숫자의 합을 구해 그 수가 소수인지 판별하면 된다.

 

 

 

2. 소수 판별

소수를 판별하는 방법에는 여러 가지가 있다.

가장 간편하면서 유명한 방법으로는 '아리스토텔레스의 체'를 사용하는 방법이 있으며 이 풀이에서도 '아리스토텔레스의 체'를 사용한다.

 

또 다른 방법으로는 페르마의 마지막 정리 등의 이론을 이용한 의사 소수를 판별하는 방법으로 판별하고자 하는 수를 다양한 검증을 통해 소수일 확률이 굉장히 높다면 소수라고 판별하는 방법이다.

 

두 방법의 장단점은 아리스토텔레스의 체를 이용한 방법은 간단하며 소수 판별이 빠르지만 메모리를 많이 차지하기 때문에 아주 큰 수를 판별하기에는 부적합 한 단점이 있다. 하지만 이 문제에서는 최대 3000까지의 수 중 확인하면 되기 때문에 선택한 방법이다.

의사 소수 판별 방법은 여러 검증을 거쳐야 하기 때문에 비교적 시간이 오래 걸리지만 메모리가 많이 필요하지 않고 아주 큰 수를 판별하기 적합하다. 그렇기 때문에 두 소수의 곱을 사용하는 공개키 암호인 RSA 에서 사용하는 방법이다.

2020.06.18 - [알고리즘/RSA] - [RSA] RSA에 사용되는 알고리즘

[RSA] RSA에 사용되는 알고리즘

 

자세한 방법은 인터넷에 검색해보면 많이 나오기 때문에 생략한다.

 

# 아리스토텔레스의 체 반환
def aristoSieve(size):
    aristo = [True] * (size + 1)
    aristo[0], aristo[1] = False, False
    
    # 1 ~ 1000까지의 아리스토텔레스의 체
    for i in range(2, int(size ** 0.5) + 1):
        if aristo[i] == True:
            for j in range(i + i, size + 1, i):
                aristo[j] = False
                
    return aristo

 

처음에는 매개변수로 판별하고자 하는 수를 입력하여 return 값으로 True / False 를 반환했었는데 생각해보니 3개의 조합된 모든 경우를 판별해야 하는 문제이기 때문에 소수를 판별할 때마다 아리스토텔레스의 체를 만드는 것은 비효율적이라 생각되어 한번 만들어진 체를 반환하여 여러 번 사용하도록 구성하였다.

그렇기에 매개변수로 체의 크기만 입력 받도록 하였고, 

첫 번째 for문의 range에서 int(size ** 0.5)를 한 부분이 있다. 이 부분은 size의 제곱근을 구하는 것인데 그 이유에 대해서도 구글에 검색해보면 많은 정보가 있기 때문에 생략한다.

 

 

 

소스코드

from itertools import combinations

# 아리스토텔레스의 체 반환
def aristoSieve(size):
    aristo = [True] * (size + 1)
    aristo[0], aristo[1] = False, False
    
    # 1 ~ 1000까지의 아리스토텔레스의 체
    for i in range(2, int(size ** 0.5) + 1):
        if aristo[i] == True:
            for j in range(i + i, size + 1, i):
                aristo[j] = False
                
    return aristo

# 솔루션 함수
def solution(nums):
    answer = 0
    # 아리스토 체 생성
    aristo = aristoSieve(3000)
    # 숫자 3개를 조합해서 나오는 것을 출력
    combi = list(combinations(nums, 3))
    
    for case in combi:
        if aristo[sum(case)]:
            answer += 1

    return answer

 

문제의 제한사항에서 숫자는 1 이상 1000 이하라고 했기 때문에 998 + 999 + 1000 = 2997 이 최대 숫자이다.

그렇기에 아리스토텔레스의 체 크기를 3000으로 주었다. (2997로 해도 된다)

aristo에는 체를 저장하고, combi에는 숫자 3개의 조합을 저장하여 각 경우를 aristo에서 소수인지 아닌지 판별 후 소수라면 answer에 1씩 더해서 마지막에 개수를 return 하는 구조이다.