[프로그래머스] 소수 만들기 Python Code

프로그래머스의 소수 만들기를 파이썬으로 풀어보겠다.

 

소수란 1과 자신으로만 나누어지는 1보다 큰 자연수이다.

 

이 문제에서는 소수, 조합에 대한 이해가 필요하다.

 

python으로 문제를 풀어보겠다 

---

문제

 

여기서 필요한 것은 리스트에서 3개를 뽑는 기능(조합), 소수 판별 기능이다.

 

여기서 조합 기능은 itertools의 combination을 사용할 것이다.

해당 함수는 아래 링크에서 확인 가능하다.

https://docs.python.org/ko/3/library/itertools.html#itertools.combinations

 

구현 순서는

1. 조합 리스트에 가능한 조합들을 넣고

2. 해당 리스트를 돌며 합을 구해 소수인지 판별하고

3. 소수라면 answer에 더해줄 것이다.

 

---

 

Code

from itertools import combinations

def solution(nums):
    answer = 0
    for n1, n2, n3 in list(combinations(nums,3)):
        sum = n1+n2+n3
        primes=[i for i in range(1,int(sum**(0.5))+1) if sum%i==0]
        if len(primes)<=1:
            answer +=1

    return answer

 

 

튜플로 반환되는 조합들을 list로 변경해서 iteration을 한다.

 

소수를 판별할 때 시간을 줄이기 위해

자연수 N을 1부터 N**0.5까지만 나누어서 리스트에 추가를 해줬다.

 

소수는 1과 자신으로만 나누어지는 자연수이기 때문에 나눈 값이 1개 이하라면 소수이다.

 

위의 방법이 가장 베스트로 보이고 combination을 쓰지 않은 다른 사람의 코드는 아래와 같다.

 

def solution(nums):
    answer = []
    result = False
    num = list(set(nums))
    if len(num)>=3 and len(num)<=50:
        for i, n in enumerate(num):
            if n<1 or n>1000:
                break
            else:
                for j in range(i+1, len(num)):
                    for m in range(j+1, len(num)):
                        sum = num[i]+num[j]+num[m]
                        for k in range(2,sum):
                            if sum%k == 0:
                                result = False
                                break
                            else:
                                result = True
                        if result == True:
                            answer.append(sum)
    c = len(answer)
    return c

 

이 코드를 보고 내가 소수의 정의를 너무 갇혀서 생각한 것도 있는 것 같다.

 

다음에 소수를 판별할 때 참고해야겠다.