1월 5일 TIL - 프로그래머스 소수 만들기

# https://school.programmers.co.kr/learn/courses/30/lessons/12977
# 소수 만들기
# 문제 설명
# 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
# 제한사항
# nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
# nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

🧐  문제 정리

1. 먼저 주어진 리스트에서 3개를 뽑아 더한다.

2. 더한 값이 소수인지 판별한다.

 

🤯  해결 과정에서의 어려움

주어진 리스트에서 서로 다른 3개를 뽑기 위해서 먼저 몇개의 조합이 나올지 계산한 다음, 그 수만큼 랜덤으로 뽑으면 되지 않을까 생각했다. 하지만 그렇게 진행할시 중복의 위험이 있다. 아니면 중첩 for문을 이용하여 리스트 하나씩 만들어 가는거다. 이렇게 하면 시간이 너무 오래걸릴 것 같다.

 

🤩  배운점

Python에는 아주 유용한 itertools이 있다. 이 모듈은 효율적인 루핑을 위한 이터레이터를 만든다. 다양한 함수를 포함하고 있지만 지금 문제에선 combinations()를 활용할 수 있다. 이 외에도 순열 등 유용한 함수들이 많다. 다음 기회에 더 자세하게 파헤쳐 보도록 하겠다.

import itertools

#입력한 iterable에서 요소의 길이 r 서브 시퀀스들을 반환한다.
itertools.combinations(iterable, r)

# 예시
list = ['A', 'B', 'C']
nCr = itertools.combinations(list, 2)
print(list(nCr)) #[('A', 'B'), ('A', 'C'), ('B', 'C')]

 

😎  해결 하기

1. 주어진 리스트에서 3개를 뽑아 더한다.

# intertools의 combinations()를 활용하면 간단하게 조합을 구성할 수 있다.
import itertools

# 주어진 리스트
nums = [1, 2, 7, 6, 4]

# 주어진 숫자 중 3개를 뽑아서 더하기
ncr = list(itertools.combinations(nums, 3))

for n in ncr:
    num = sum(n)
    # 소수 판별하기

 

2. 소수 판별하기

소수를 찾는 것은 전에 문제를 푼적이 있다. 먼저 약수의 존재를 확인하려고 1부터 n까지 for문으로 돌려서 n을 나눌수 있는지 판별했었다. 하지만 시간이 너무 오래걸렸고 약수는 대칭으로 존재하기 때문에 제곱근을 구해 제곱근까지의 숫자로 판별하였다. 이때 제곱근이 정수라면 소수가 아니다.

# 소수 개수 확인
count = 0
for n in ncr:
    num = sum(n)
    # 소수 판별하기
    check = True
    # 제곱근이 정수라면 소수가 아니기에 정수가 아닌 숫자만 판별한다.
    if math.sqrt(num) != int:
        # 제곱근까지의 숫자 중 약수가 존재하는지 확인하기.
        for number in range(2, int(math.sqrt(num) + 1)):
            if num % number == 0:
                check = False
                break
        if check:
            count += 1

 

📝   최종 함수

import math
import itertools

def solution(nums):
    ncr = list(itertools.combinations(nums, 3))
    count = 0
    for n in ncr:
        num = sum(n)
        check = True
        if math.sqrt(num) != int:
            for number in range(2, int(math.sqrt(num) + 1)):
                if num % number == 0:
                    check = False
                    break
            if check:
                count += 1
    return count