[프로그래머스] 소수 만들기

🔒 문제

문제 설명

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

제한사항

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

---

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

---

🔓 풀이

🔑 요구사항 파악

1. 요구사항 : 서로 다른 nums의 원소 3개를 골라 더했을 때 소수가 되는 경우의 개수를 리턴

2. Type

 - Input | nums: List[int] (3 <= len(nums) <= 50)

 - Output | answer: int

 

---

🔑 문제 정의

1. List 원소 3개 뽑아서 더하기

2. 소수 판별하기

 

---

🔑 문제 해결 방법 고민하기

1. List 원소 3개 뽑아서 더하기
 - for문을 3번 반복해서 해결?
 - for문을 반복할 때 중복이 생길 수 있다.

2. 소수 판별하기
 - x를 2로 나누고 2~(x/2) 까지의 정수로 나눠서 전부 나머지가 0이 아니면 소수

 

<고민의 흔적>

 

---

🔑 문제 해결 / 코드

nums = [1,2,7,6,4]

def solution(nums):
    answer = 0

    for first in range(0, len(nums)-2):
        for second in range(first+1, len(nums)-1):
            for third in range(second+1, len(nums)):
                sum_num = nums[first] + nums[second] + nums[third]
                # 소수 판별하기 
                for i in range(2, round(sum_num/2)):
                    if sum_num % i == 0:
                        break
                else:
                    answer += 1
    return answer

print(solution(nums))

 

---

💉 피드백

1. for문 4번 사용

 원소뽑을 때 3번, 소수 구할 때 1번, 총 4번의 for문을 사용해서 가독성과 성능(시간 복잡도) 모두 안 좋은 코드라고 생각했는데 다른 사람의 풀이에서 새로운 함수를 배울 수 있었다. 

from itertools import combinations as cb

for a in cb(nums, 3):
    cand = sum(a)

combinations( ) 인자로 list와 int 정보를 넣어주면 list에서 int 만큼 원소를 추출한 list가 반환되는 것으로 보인다. 이번에 블로깅 중인 파이썬 내장 함수 zip( )이 끝나면 어떤 함수인지 파헤쳐 봐야겠다. (for문을 줄일 수 있는 함수라니 이건 필수지,,)

 

2. 중복된 원소가 뽑히지 않게 제한할 때 

 for문을 3번 사용해서 nums의 원소를 추출하게 되면 같은 원소를 두번 이상 추출하는 상황이 생긴다. 바로 중복된 원소를 참조하는 건데 나는 이 문제를 해결하기 위해서 각 for문마다 range 값에 조건을 줘서 중복되지 않게 방지했다.

실제로 내가 작성한 코드의 각 원소를 프린트해보면,

nums = [1,2,7,6,4]

def solution(nums):
    answer = 0

    for first in range(0, len(nums)-2):
        for second in range(first+1, len(nums)-1):
            for third in range(second+1, len(nums)):
            	# 원소 프린트
                print(nums[first], nums[second], nums[third])
                sum_num = nums[first] + nums[second] + nums[third]
                # 소수 판별하기
                for i in range(2, round(sum_num/2)):
                    if sum_num % i == 0:
                        break
                else:
                    answer += 1
    return answer

print(solution(nums))

 

다른 풀이를 보니 range(x, y)에서 대부분 x에서 조건을 줘서 문제를 해결했는데 나는 x, y 모두 조건을 걸었다. 사실 y 조건은 필요가 없던셈,, 곰곰이 생각해보니 x 조건으로 인해서 x >= y 같은 상황이 되면 range 크기가 0이 돼서 for문이 종료되고 알아서 예외처리가 된다. 

 

3. 소수 판별법

나는 주어진 정수 n을 2로 나누어 2부터 n/2 까지의 정수로 모두 나누어 소수를 구했는데 더 효율적인 방법이 존재한다. 

n의 제곱근을 구해서 2부터 n의 제곱근 까지의 정수로 소수를 구하는 방법과 아리스토텔레스의 체를 사용한 방법 등이 있는데 소수를 구하는 알고리즘 문제가 많은 만큼 한번 정리해서 공부할 필요성이 있다.

 

---

📌 도전 과제

1. combinations( ) 함수 공부하기

2. 소수 구하는 알고리즘 공부하기