[프로그래머스] 소수 만들기 문제풀이 python

🐒 문제

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

✍ 나의 풀이

from itertools import combinations

def sosu(parm):
    a = [True] * parm
    a[0],a[1] = False,False
    
    for i in range(2,int(parm**(1/2))+1):
        if a[i]:
            multp = 2
            while i*multp < parm:
                a[i * multp] = False
                multp += 1
    return a

def solution(nums):
    answer = 0
    arr = list(map(sum,combinations(nums,3)))
    sosuarr = sosu(max(arr)+1)

    for i in arr:
        if sosuarr[i]:
            answer += 1

    return answer

소수판별에서 버벅임

---

🧠 문제 이해

주어진 수열에서 3개를 뽑아 합한값이 소수인 경우는 몇 가지인가?

순서없이 r 개를 뽑는 경우의 수 >> combinations

경우의 수마다 소수를 판별하면 시간이 오래 걸리니

미리 소수를 구해놓자.

소수 판별 >> 에라토스테네스 의 체

nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

위 조건에 따라 발생할 수 있는 경우의 수 중 최대값은 48,775

그러면 항상 48,775 까지 소수판별을 해놓아야 할까?

>> 주어진 수열에서 3개를 뽑아 합한값 중 최대값까지만 소수를 판별해 놓는다.

이후 구해놓은 소수를 이용해 각 경우의 수가 소수인지를 센다.

from itertools import combinations

def sosu(parm):	 # parm까지만 소수를 구하는 함수
    a = [True] * parm
    a[0],a[1] = False,False		# 0과 1은 소수가 아님
    
    for i in range(2,int(parm**(1/2))+1):
    	# 약수의 성질 때문에 param의 제곱근 + 1까지만 소수를 판별해도 모든 값을 판별할 수 있음
        if a[i]:	# i가 소수라면 i의 배수는 소수가 될 수 없음
            multp = 2
            while i*multp < parm: # i의 배수가 parm 을 넘기 전까지만 계산
                a[i * multp] = False
                multp += 1
    return a

def solution(nums):
    answer = 0 # 경우의 수 중 소수가 몇 개인지 저장하는 변수
    
    arr = list(map(sum,combinations(nums,3)))	
    	# combination >> nums에서 순서없이 3 개를 뽑은 값을
     	 # list(map(sum, >> 합해서 하나씩 리스트에 담아줌
         
    sosuarr = sosu(max(arr)+1)
    	# 경우의 수의 합중 최대값까지 소수를 판별함
         # +1 하는 이유는 요소와 배열 길이를 맞춰주기 위함

    for i in arr:	# 경우의 수의 합들 에서 하나씩 확인
        if sosuarr[i]:	# 소수라면
            answer += 1		# 갯수 1 증가

    return answer

정확성  테스트
테스트 1 〉	통과 (0.43ms, 10.3MB)
테스트 2 〉	통과 (0.55ms, 10.3MB)
테스트 3 〉	통과 (0.14ms, 10.3MB)
테스트 4 〉	통과 (0.11ms, 10MB)
테스트 5 〉	통과 (0.60ms, 10.2MB)
테스트 6 〉	통과 (1.43ms, 10.5MB)
테스트 7 〉	통과 (0.55ms, 10.2MB)
테스트 8 〉	통과 (2.58ms, 10.6MB)
테스트 9 〉	통과 (0.70ms, 10.3MB)
테스트 10 〉	통과 (2.49ms, 10.4MB)
테스트 11 〉	통과 (0.10ms, 10.3MB)
테스트 12 〉	통과 (0.05ms, 10.2MB)
테스트 13 〉	통과 (0.06ms, 10.3MB)
테스트 14 〉	통과 (0.05ms, 10.2MB)
테스트 15 〉	통과 (0.04ms, 10.2MB)
테스트 16 〉	통과 (4.00ms, 10.6MB)
테스트 17 〉	통과 (4.47ms, 10.7MB)
테스트 18 〉	통과 (1.84ms, 10.3MB)
테스트 19 〉	통과 (1.92ms, 10.4MB)
테스트 20 〉	통과 (4.59ms, 10.7MB)
테스트 21 〉	통과 (4.49ms, 10.8MB)
테스트 22 〉	통과 (2.20ms, 10.4MB)
테스트 23 〉	통과 (0.02ms, 10.2MB)
테스트 24 〉	통과 (4.06ms, 10.4MB)
테스트 25 〉	통과 (3.90ms, 10.5MB)
테스트 26 〉	통과 (0.01ms, 10.2MB)

---