[프로그래머스] 세 소수의 합

로직

• 소수를 구하기 위해 에라토스테네스의 체를 사용하였다.
• 우리는 n = 1st 소수 + 2nd 소수 + 3rd 소수 를 구하는 것이기 때문에, n은 최소 10이상이어야한다.
• max_num은 구해야할 소수 중 가장 큰 값을 뜻하는데 이를 n-5로 설정해준 이유는, 1st 소수 + 2nd 소수 의 최솟값이 5이기 때문이다.

1. 에라토스테네스의 체를 이용해서 소수를 구한다. O(n^2)
   1. nums 리스트를 모두 True로 설정 (nums의 사이즈는 max_num +1 : 인덱스와 소수를 일치시키기 위함)
   2. 2부터 끝까지 순회하며 True인 경우에는 소수로 간주하고 소수의 배수가 되는 숫자들은 모두 False로 바꾼다.
2. 서로다른 세 소수들의 합이 n이 되는 경우의 수를 모두 구한다 O(n^2)
   1. nested loop을 도는데 첫 번째 loop은 처음부터 max_num -2 까지 순회한다(x)
   2. 두 번째 loop은 x+1부터 max_num-1까지 순회한다. (y)
   3. 그리고 n - (x + y) 값이 prime 안에 있다면 (해당 값, x, y) 경우의 수가 하나 추가된다.
   4. # 단, (2, 3, 7)과 (3, 2, 7)은 같아야하기 때문에 sorted()를 통해서 중복되는 값이 나오지 않게끔 해주었다.

 

 

 

코드

 

from collections import deque
def solution(n):
    answer = dict()
    # 1. prime을 담을 stack
    prime = set()
    
    # 2. n이 10미만이면 무조건 0
    if n < 10:
        return len(answer)
    
    # 3. 에라토스테네스 체를 이용해 소수를 구한다.
    max_num = n-5
    
    nums = [True] * (max_num+1)
    nums[1] = False
    for i in range(2, max_num+1):
        if nums[i]:
            prime.add(i)
            for j in range(2*i, max_num+1, i):
                nums[j] = False
                
    # 4. 합이 n이 되는 소수들의 경우의 수 구하기 
    prime_list = list(prime)
    for x in range(len(prime)-2):
        for y in range(x+1, len(prime)-1):
            first, second = prime_list[x], prime_list[y]
            thrid = n - (first + second)
            # prime에서 뽑아낸 수가 first, second이다.
            # thrid = n - (first + seond) 가 만약 prime이면 경우의 수 +1
            if thrid in prime and (thrid not in [first, second]):
                sum_is_n = tuple(sorted([first, second, thrid]))
                answer[sum_is_n] = True

    return len(answer)