규도자 개발 블로그

[프로그래머스/Level1/파이썬3(python3)] 소수 만들기 본문

알고리즘/풀이

[프로그래머스/Level1/파이썬3(python3)] 소수 만들기

규도자 (gyudoza) 2021. 3. 9. 22:25

[프로그래머스/Level1/파이썬3(python3)] 소수 만들기

문제

주어진 숫자 중 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을 만들 수 있습니다.

풀이

from itertools import combinations


def solution(nums):
    answer = 0
    cmb = list(combinations(nums, 3))
    for number_set in cmb:
        current_number = sum(number_set)
        current_number_prime = True
        for i in range(2, int(current_number ** 0.5) + 1):
            if current_number % i == 0:
                current_number_prime = False
        if current_number_prime:
            answer += 1
    return answer

설명

원래 3중 반복문으로 번호의 조합을 모두 선택하는 식으로 했다가 뭔가 모양이 미워서(?) 다른 사람들은 어떻게 풀었나 찾아봤고, 수 배열이 있을 때 그 수를 n개 선택하는 경우의 수 조합을 모두 리턴해주는 combinations라는 함수가 있다는 걸 발견했다. 우오오 대박. 그 함수를 이용해서 예전에 에라토스 테네스의 체를 공부했을 때 깨달은, 자연수 n은 루트n까지 나눠보면 소수 판별 여부를 알 수 있다라는 공식을 이용해서 n이 해당 수까지 나누어 떨어지는지 검사하는 식으로 풀어냈다.

 

팁: 파이썬의 **연산은 제곱이다. 그런 고로 math패키지의 sqrt함수를 쓰지 않더라도 n ** 0.5를 하면 n의 제곱근을 알 수 있다.

0 Comments
댓글쓰기 폼