Programmers - 소수 만들기[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

문제 설명

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

제한사항

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

 

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

 

입출력 예 설명

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

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

---

문제 풀이

python에서 제공하는 combinations 메서드와 소수 판별 메서드를 정의하여 문제를 풀었다.

주어진 수중 3개의 수의 합이 소수 인지 판별하면 되므로 주어진 수에서 3개를 뽑는 조합을 구하여 해당 수들의 합이 소수인지 아닌지 판별하여 count 하면 답을 구할 수 있다.

n = 50인 최악의 경우 조합을 구하면 50C3으로 19600개의 수를 비교하면 되므로 충분히 모든 수를 비교 할 수 있다.

소수인지 판별하는 방법은 시간을 최적화 하기 위해 2부터 해당 수의 제곱근까지만 순회하며 해당 수가 나누어 떨어지지 않는다면 소수 나누어 떨어진다면 소수가 아닌 수로 판별할 수 있다.

 

구현 코드

코드 링크 : 소수 만들기

from itertools import combinations
import math

def is_prime_number(x):
    #2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x))+1):
        #x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

def solution(nums):
    answer = 0
    for x in combinations(nums, 3):
        if is_prime_number(sum(x)):
            answer += 1

    return answer