[프로그래머스/LV.1] 소수 만들기

문제 설명

주어진 숫자 중 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을 만들 수 있습니다.

---

내 풀이

def solution(nums):
    
    answer=0
    for a in range(len(nums)-2):
        for b in range(a+1,len(nums)-1):
            for c in range(b+1,len(nums)):
                i = nums[a]+nums[b]+nums[c]
                for j in range(2,i):
                    if i%j==0:
                        break
                else:
                    answer+=1
            
    return answer

세가지 수의 합에 대한 경우의 수니

a,b,c를 매개변수로 for문을 총 3번 돌리며 하나씩 쏙쏙 뽑을 수 있게..

중복되게 뽑을 수 없으니 (비복원추출)

범위는 각각 (0,배열의길이-2), (a+1,배열의길이-1), (b+1,배열의길이)

각 매개변수를 인덱스로 갖는 배열값의 합을 i 에 저장한다!

 

소수는 1과 자기 자신만을 약수로 갖는 수이니

1을 제외한 범위에서 자기자신(i)로 나누었을때만 나누어 떨어지면 된다.

즉 2부터 i-1까지 (2,i) i를 나누었을때

나머지가 0인 경우가 없으면 된다는 것!

i%j==0  : 2부터 i 사이에 나누어 떨어지는 수가 있다

             -> 소수아님 -> break

i%j 이 모두 0이 아니다 : 2부터 i 사이에 나누어 떨어지는 수가 없다

             -> 소수! -> answer에 1씩 추가 (case 갯수세기)

 

 

 

다른사람 풀이 #1

def solution(nums):
    from itertools import combinations as cb
    answer = 0
    for a in cb(nums, 3):
        cand = sum(a)
        for j in range(2, cand):
            if cand%j==0:
                break
        else:
            answer += 1
    return answer

이전문제를 풀 때도 나왔던 itertools의 combination 함수!

combination 은 리스트 내 모든 조합을 구하는 함수!

(리스트에서 n개의 요소의 합에 대한 모든 조합)

from itertools import combination
list(combination(리스트명,n))

함수 이름을 cb로 지정하고

cb(nums,3)  #nums 리스트 내 3개요소의 합의 모든 조합을 구한다.

그 다음은 내가 푼것과 같은 맥락.

 

for문을 여러개 중첩하고 범위를 복잡하게 지정하지 않아도

combination 함수를 이용해서 더 간편하게 조합을 구할 수 있다!

 

그런데 나도, 이 풀이도 유일한(?) 단점은

어쨌든 for문의 중첩이란 것!

시간이 오래걸려 효율이 굉장히 떨어진다고한다 ㅠㅠ 

 

 

 

다른사람 풀이 #2

from itertools import combinations
def prime_number(x):
    answer = 0
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            answer+=1
    return 1 if answer==1 else 0

def solution(nums):
    return sum([prime_number(sum(c)) for c in combinations(nums,3)])

x**0.5 는 x의 0.5승, 즉 루트 x값이다.

주어진 자연수x에 대해서 1보다 크고 루트x 이하인

모든 자연수들로 나누어떨어지지 않으면 소수다! 라는 보편적인 소수 판별법중 하나이다.

answer값이 1이면 (=루트x이하인 자연수 중 나누어 떨어지는 숫자가 1뿐이면)

소수 -> return 1

그렇지않으면(else) -> return 0