summer/winter coding > 소수만들기

문제 설명

주어진 숫자 중 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을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

=> 풀이

1. 조합을 이용하여 nums의 수들 중 3개의 수를 뽑은 경우의 수를 만든다. (nCr)

2. 그 경우의 수들을 더한 값이 소수인지 체크한다.

3. 소수인 경우 답인 리스트에 대입.

 

def combination(array, r):
    chosen = []
    
    if r > len(array):
        return chosen

    if r == 1:
        for i in array:
            chosen.append(i)

    elif r > 1:
        # r 개 만큼 빼주는 이유 (순서가 고려사항이 아니기 때문에, r개는 고려하지 않아도 앞서서 정해진다)
        for i in range(len(array) - r + 1):
            for temp in combination(array[i + 1:], r - 1):
                chosen.append([array[i], temp])
    return chosen

def prime_number(num): #소수 체크 함수
    if num != 1:
        for f in range(2,num):
            if num % f == 0:
                return False
            
    else: #num == 1
                return False

    return True

def solution(nums): #main
    print(nums)
    a = combination(nums, 3)
    s = []
    count = 0

    for i in range(len(a)):
        s.append(a[i][0] + a[i][1][0] + a[i][1][1])

    for i in s:
        if prime_number(i):
            count += 1
    
    return count

 

문제 

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

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