08.13. 프로그래머스 : 소수 만들기

🔎 소수 만들기

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하라.

"""
1. 주어진 숫자로 3개의 수를 더해서 겹치지 않는 combi 리스트로 만든다.
2. 소수를 구하는 함수
3. combi 리스트에서 숫자 하나씩을 뽑아 prime 함수로 보내어 소수인지 판별하는 함수
"""

💡 문제풀이#1

위 1, 2, 3번에 충실한 함수를 작성해봤다.
itertools의 함수인 combinations으로 배열의 3개 숫자 조합의 경우를 모두 만들 수 있다.
그 후 0번, 1번, 2번에 위치한 숫자를 모두 더하여 새로운 리스트에 추가해주었다.
여기에서 중복이 되는 숫자를 걸러주었다. (실패의 원인)

def combi(nums):
    prime_list = []
    combi_list = list(itertools.combinations(nums, 3))
    for i in combi_list:
        num3 = i[0] + i[1] + i[2]
        if not num3 in prime_list:
            prime_list.append(num3)
    return prime_list

def prime(n):
    root = int(n**0.5)
    for i in range(2, root + 1):
        if n % i == 0:
            return False
    return True

def solution(nums):
    answer = 0
    for n in combi(nums):
        if prime(n) == True:
            answer += 1
    return answer

💡 문제풀이#2

중복된 숫자더라도 그 조합에 쓰인 숫자가 다르기 때문에, 이를 거르면 안되는 문제였다.

def combi(nums):
    prime_list = []
    combi_list = list(itertools.combinations(nums, 3))
    for i in combi_list:
        num3 = i[0] + i[1] + i[2]
#       if not num3 in prime_list:
#           prime_list.append(num3)
    return prime_list

# 테스트 20 : 통과 (32.82ms, 12.2MB) 

💡 문제풀이#3

팀원분이 sum 함수를 통해 획기적으로 테스트 실행 시간을 줄이셨길래 combi 함수를 sum으로 변경해봤다. 약간의 차이가 났지만 시간과 메모리가 줄어든 것을 확인할 수 있었다.

def combi(nums):
    prime_list = []
    combi_list = list(itertools.combinations(nums, 3))
    for i in combi_list:
        prime_list.append(sum(i))      
    return prime_list

# 테스트 20 : 통과 (30.03ms, 12.1MB)

💡 문제풀이#4

팀원분의 풀이에서 인상깊었던 sum 함수를 활용하며 combi함수와 solution 함수를 합쳐서 표현해봤다.  시간과 공간이 획기적으로 줄어들었다. 

import itertools

def prime(n):
    root = int(n ** 0.5)
    for i in range(2, root + 1):
        if n % i == 0:
            return False
    return True

def solution(nums):
    answer = 0
    combi_list = list(itertools.combinations(nums, 3))
    for n in combi_list:
        sum_n = sum(n)
        if prime(sum_n) == True:
            answer += 1
    return answer

# 테스트 20 : 통과 (18.53ms, 11.2MB)

💡 배운 점

지난 소수 문제 풀이에서 변수할당 및 코드 최적화하기에 대한 이야기를 했었는데, 모든 함수를 나눈다고해서 최적화가 되는 것도 아니다. 꼭 필요한 곳에서 분리가 되어야 한다는 점을 기억하자!