Summer/Winter Coding - # 1. 소수 만들기

코딩 테스트 연습 - 소수 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

1. 소수 만들기

문제 설명

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

제한사항

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

---

입출력 예numsresult

[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. 3개의 값을 더하기 위해 3개를 뽑아내는 코딩이 필요하다 => 조합 이용

2. 뽑은 다음 더하고

3. 소수인지 판단하는 알고리즘 또한 필요

4. 소수이면 정답 + 1

 

* 조합은 라이브러리를 사용해도 된다. 하지만 나는 재귀를 이용해서 내가 직접 구현해 보았다*

 

---

[코드]

 

def creatCombi(arr, n):
    result =[]
    if n == 0:
        return [[]]

    for i in range(0, len(arr)):
        el = arr[i]
        restArr = arr[i + 1:]
        for res in creatCombi(restArr, n - 1):
            result.append([el] + res)

    return result


def checkSosu(summary):
    for i in range(2, summary - 1):
        if summary % i == 0:
            return False
    return True


def solution(nums):
    answer = 0
    # 3개의 조합
    res = creatCombi(nums, 3)
    
    for r in res:
        # 더한다음
        summary = sum(r)
        # 소수인지 체크
        if checkSosu(summary):
            answer += 1

    return answer

---

후기

 

조합 라이브러리를 쓰면 5분 안에 풀 수 있을 것이다.

나도 너무 쉽다고 느껴서 내가 직접 구현해봤다.

사실 조합이랑 순열 구현은 막상 하려고 하면 잘 안됬던 기억이 있기에

이참에 한 번 더 구현해봤다.