Level 2 소수만들기 Python 3

programmers.co.kr/learn/courses/30/lessons/12977?language=python3

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

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms/blob/main/README.md

hwayeon351/Programmers-Algorithms

from itertools import combinations
from math import sqrt

def solution(nums):
    answer = 0
    combi = combinations(nums, 3)
    for c in combi:
        c_sum = sum(c)
        num = int(sqrt(c_sum))+1
        i = 1
        check = True
        for i in range(2, num + 1):
            if c_sum % i == 0:
                check = False
                break
        if check:
            answer += 1
    return answer

 

---

풀이 과정

풀이 시간  10분

1. 조합 구하기 itertools.combinations()

 먼저, nums 중 3개의 숫자를 뽑는 모든 경우의 수를 만들어 줘야 한다.

파이썬에서는 itertools 라이브러리의 순열 permutations()과 조합 combinations()를 활용할 수 있다. (아래 참고 자료를 참고하자.)

이 문제는 순서와 상관 없이 서로 다른 3개의 숫자를 뽑아야 하기 때문에 조합인 combinations() 함수를 활용했다.

form itertools import combinations

combi = combinations(nums, 3)
print(list(combi))

combination(반복 가능한 객체, r)을 하면 반복 가능한 객체에서 중복을 허용하지 않고 r개의 객체를 뽑는다.

print(list(combi))를 해보면 리스트 안에 담긴 튜플 형태의 조합 결과를 살펴 볼 수 있다.

 

 

2. 소수 판별

 그렇다면, 이제 combi로 만든 조합의 합들이 소수인지 판별해보자.

소수란, 1과 자기 자신을 제외한 2보다 큰 자연수로 나누어 떨어지지 않는 자연수를 말한다.

이에 따라, 자연수 N이 소수인지 아닌지 판별하기 위해서 2부터 N-1을 모두 나누어 나머지가 0인지 판별할 수 있다.

하지만, N이 커지면 비효율적일 것이다.

 

 만약, a x b = N (a < b)이라고 해보자. 이 경우, N은 a와 b로 나누어 떨어지기 때문에 소수가 아니다. 여기에서 우리는 a로 나누어 떨어지면 소수임을 알 수 있기 때문에 굳이 b까지 나누어 볼 필요가 없다는 것을 알 수 있다.

따라서, 2부터 N의 제곱근 + 1 까지만 N을 나누어 보면 훨씬 더 효율적으로 소수를 판별할 수 있다는 것이다.

 

 문제에서 nums에는 중복되지 않는 3개 이상의 숫자가 들어있으며, 각 숫자는 1 이상 1,000 이하의 자연수로 되어있다고 했다.

따라서, 숫자 3개의 조합의 합이 무조건 2 이상이기 때문에, 2부터 나누어 나가면 된다.

파이썬에서는 제곱근을 구하는 함수 sqrt()가 math 라이브러리에 내장되어 있다. (아래 참고 자료를 참고하자.)

 그렇다면, 이제 이를 파이썬 코드로 구현해보자.

    for c in combi:
        c_sum = sum(c)
        num = int(sqrt(c_sum))+1
        i = 1
        check = True
        for i in range(2, num + 1):
            if c_sum % i == 0:
                check = False
                break
        if check:
            answer += 1

 1.에서 구한 combi 안에 모든 조합들이 튜플 형태(반복 가능한 객체)로 저장되어있다. 따라서, for문을 활용해 각 조합 튜플을 c에 담아준다. sum(c)를 c_sum에 담아주고, c_sum의 제곱근(int형) + 1을 한 결과를 num에 저장해준다.

그 다음, check = True를 해주고 2부터 num까지의 수로 c_sum을 나누어본다. 이때, 나누어 떨어지면 Check = False로 바꾸어주고 break하여 안의 for문을 벗어나도록 한다.

안의 for문이 다 돌면, check의 상태를 체크하여 True이면 c_sum이 소수임을 의미하므로 answer += 1 해준다.

 

---

참고

• 2021/01/21 - [Python/라이브러리] - itertools

itertools

• 2021/01/14 - [Python/라이브러리] - math

math