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

오랜만에 시작해본 알고리즘 풀이

 

첫 문제는 LEVEL 1 문제인 소수 만들기를 풀어볼까 한다.

 

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

프로그래머스

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예시(기본 테스트 케이스)

 

     input            output 

	nums	result
예제1번	[1,2,3,4]	1
예제2번	[1,2,7,6,4]	4

 

문제를 이해해보자면 다음과 같다. 

주어지는 숫자는 3~50개 사이로 배열 형태(list type)로 주어지며

이 숫자 중 3개를 뽑아 더한 값이 소수인 경우를 출력하면 된다. 

 

수학을 잘 못하는 나는 일단 단계별로 분리를 해보기로 했다.

 

1. 3~ 50개 숫자 중 3개 뽑기 

순서와 상관없이 3개의 숫자를 뽑으므로 조합(Combination)이다. 

      n 개의 숫자가 입력됐다고 보면. \( nC3 \) 개의 조합이 나온다.

> python은 조합으로 추출된 값들을 보여주는 함수가 있어 해당 함수를 사용한다.

 

2. 뽑은 3 숫자를 더하기

뽑은 3개의 숫자를 각각 더한 값들을 배열에 저장한다. 배열의 크기는 \( nC3 \) 

 

3. 더한 값이 저장되어있는 배열을 돌며 소수를 확인한다. 

소수이면 result값을 +1 한다.

     ❁소수는 1과 자신만을 약수로 가지는 수이다.

> n이 소수인지 판별하려면 2... n-1로 나누었을 때 나누어 떨어지지 않아야 한다. 

---

입출력 예시를 분석해보자

 

예제 1번)

입력값이 [1. 2, 3, 4] 이면 조합으로 구할 수 있는 경우는 총 네 가지이다. 

1, 2, 3

1, 2, 4

1, 3, 4

2, 3, 4

각각 더해보면 다음과 같다.

6

7

8

9

위 숫자 중 소수는 7밖에 없으므로 result는 1이어야 한다. (1개만 소수이다)

---

위 내용을 토대로 파이썬 코드를 짜보았다. 

from itertools import combinations


def solution(nums):
    answer = 0
    
    C = list(combinations(nums, 3)) # 조합 구하기
    S= list() # 더한 값 배열 저장 위해 선언
    
    for i in C: # 조합별 +값 S에 저장
        S.append(sum(i))
            
    for j in S:
        for k in range(2, j): #2부터~
            if (j % k == 0): # 모두 나머지가 0이 아니여야 소수 > 0이면 break해서 다음값 탐색
                break
            if (k == j-1): # j-1까지 break 안됐으므로 소수
                answer += 1
                
    return answer

 

주의사항
❁ 위 코드는 정확성 및 시간 체크를 하지 않아 최적화되어있지 않습니다.
❁ 필자의 주 언어가 Java여서 위 코드는 문법이 파이썬스럽지 않습니다.
❁ 현재는 문제 풀어보는 것에 중점을 두고 있어 다양한 문제를 풀이 후
최적화된 소스를 업로드하겠습니다:)