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

 

---

문제

 

어떤 수를 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 구하려 합니다. 예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.

• 3+7+23
• 3+11+19
• 3+13+17
• 5+11+17

자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 return 하는 solution 함수를 작성해주세요.

제한 조건

• n은 1,000 이하인 자연수입니다.

입출력 예

n	return
33	4
9	0

 

 

---

풀이

 

에라토스테네스의 체

http://ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

2부터 N까지 소수를 구하는 간단한 방법이다.

2부터 N-1까지 자기 자신을 제외한 배수를 제외하면 된다. 

 

 

소수 리스트(prime_num) 만들기

1. 2~n까지 수를 담을 리스트 a를 생성한다.

0, 1은 필요없어서 n-3 길이의 리스트를 생성하면 되지만,

a[i] = i 일때 구현에 훨씬 편하다.

따라서 0, 1을 추가한 n-1 길이의 리스트를 생성한다.

 

2. 생성한 리스트에서 자기 자신을 제외한 나머지 배수들을 0으로 만든다.

while문을 통해 처리해줬다.

항상 이런 반복문을 처리할 때 숫자가 헷갈리기 쉬운데

반복문 안에서 무엇을 해야하는지,

반복문 종료 조건은 무엇인지,

반복문 시작 시 변수 상태는 어떤지 생각하면 된다.

 

3. a 리스트에서 0을 제외한 원소들을 prime_num에 넣어준다.

리스트 안에 for문을 넣어 간단하게 생성하자.

for문 끝에 if 문을 바로 넣어도 될까 궁금했는데 가능했다.

 

---

코딩

 

import itertools 
def solution(n):
    answer = 0
    
    if n < 10:
        return 0
        
    a = [i for i in range(n)] # [0,1,2,3,4,5,6, ....]
    a[0] = 0
    a[1] = 0
    
    for i in range(2,n):
        if a[i] == 0:
            continue
        j = i*2
        while j < n:
            a[j] = 0
            j += i
        
    prime_num = [i for i in a if i != 0]
    print(prime_num)
    
    results = itertools.combinations(prime_num, 3)
    for result in results:
        if sum(result) == n:
            answer += 1
    
    
    return answer

예외 상황

가장 작은 소수 3개의 합은 10이다.

따라서 n이 10 미만일 경우 소수 3개의 합이 n이 되는 경우는 없다.

return 0를 통해 미리 예외 상황을 제외해두자.

(이 부분을 처리하지 않으면 정확성 케이스 중 하나에서 런타임 에러가 난다.) 

 

참고: itertools에서 combinations 사용방법

1. itertools를 import하고 사용하기

import itertools
itertools.combinations(<iterable>, <r>)

2. itertools에서 combinations를 import하고 사용하기

from intertools import combinations
combinations(<iterable>, <r>)

 

combinations를 자주 사용할 것이라면 2번을 사용하는게 낫다.

 

https://devdocs.programmers.co.kr/references/python3/library/itertools.html?highlight=combination#itertools.combinations

itertools — Functions creating iterators for efficient looping — Python 3.7.2rc1 documentation

항상 공식문서를 통해 공부하자.

코딩테스트때 참고가능하기 때문에 미리 익숙해지면 좋다.

 

---

결과

 

 

정확성 테스트

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (0.13ms, 10.2MB)
테스트 5 〉	통과 (0.21ms, 10.3MB)
테스트 6 〉	통과 (0.22ms, 10.1MB)
테스트 7 〉	통과 (0.00ms, 10.2MB)
테스트 8 〉	통과 (0.00ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.54ms, 10.2MB)
테스트 11 〉	통과 (1.72ms, 10.2MB)
테스트 12 〉	통과 (8.25ms, 10.1MB)
테스트 13 〉	통과 (10.81ms, 10.2MB)
테스트 14 〉	통과 (18.84ms, 10.4MB)
테스트 15 〉	통과 (101.44ms, 10.2MB)

효율성 테스트

테스트 1 〉	통과 (39.71ms, 10.3MB)
테스트 2 〉	통과 (52.30ms, 10.2MB)
테스트 3 〉	통과 (64.66ms, 10.3MB)
테스트 4 〉	통과 (75.70ms, 10.2MB)
테스트 5 〉	통과 (100.14ms, 10.3MB)

채점 결과

정확성: 75.0

효율성: 25.0

합계: 100.0 / 100.0