[LV.3] 소수 만들기 ⭐️

문제

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

프로그래머스

---

문제 설명

• 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.
• 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때
  소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성하세요
• 제한사항
  nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
  nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

---

정답 코드

from itertools import combinations

def solution(nums):
    answer = 0
    
    # nums에서 3개를 고르는 모든 조합에 대해 반복
    for comb in combinations(nums, 3):
        total = sum(comb)  # 선택한 3개의 합 계산

        # 2부터 total의 제곱근까지 나눠서 약수 있는지 확인
        for divisor in range(2, int(total ** 0.5) + 1):
            if total % divisor == 0:  # 나누어 떨어지면 소수가 아님
                break
        else:                         # 나누어 떨어지는 수가 없으면 소수
            answer += 1               # 소수인 경우 카운트 증가
    
    return answer          # 소수가 되는 경우의 개수 반환

---

코드 설명

        # 2부터 total의 제곱근까지 나눠서 약수 있는지 확인
        for divisor in range(2, int(total ** 0.5) + 1):
            if total % divisor == 0:  # 나누어 떨어지면 소수가 아님
                break
        else:                         # 나누어 떨어지는 수가 없으면 소수
            answer += 1               # 소수인 경우 카운트 증가

 

• 예시)

---

첫 번째 시도 (실패)

def solution(nums):
    n = len(nums)
    answer = 0
    
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                total = nums[i] + nums[j] + nums[k]
                
                count = 0
                for s in range(1, total+1):
                    if total % s == 0:
                        count += 1
                        
                        if count == 2:
                            answer += 1
        
    return answer

---

문제점

- count == 2일 때 즉시 answer += 1 하면 안됨

                for s in range(1, total+1):
                    if total % s == 0:
                        count += 1
                        
                        if count == 2:
                            answer += 1   # ❌ 이 시점에서 소수라고 단정하면 안 됨

 

• count는 total의 약수 개수를 세는 변수
• 소수는 약수가 '정확히 2개'일 때만 해당 (1과 자기 자신)
• 하지만 count == 2 되는 순간은 단지 두 번째 약수가 발견된 시점일 뿐이며, 이후에 세 번째 약수가 발견될 수도 있음

---

두 번째 시도 (성공. 개선 필요)

def solution(nums):
    n = len(nums)
    answer = 0
    
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                total = nums[i] + nums[j] + nums[k]
                
                count = 0
                for s in range(1, total+1):
                    if total % s == 0:
                        count += 1
                        
                if count == 2:   # 소수일 때만
                    answer += 1
        
    return answer

---

개선점

• 소수 판별 시 제곱근까지만 확인 (효율 개선)
• 조합 구할 때 itertools.combinations 사용 (코드 간결화)