[Algorithm] [Python] Programmers - 소수 만들기

Programmers - 소수 만들기

문제 설명

---

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

제한사항

---

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

제출 코드

---

def isPrime(x):
    if x > 1:
        for i in range(2, x):
            if x % i == 0:
                return False
    else:
        return False
    return True

def solution(nums):
    num_len = len(nums)
    answer = 0
    for i in range(num_len):
        for j in range(i+1, num_len):
            for k in range(j+1, num_len):
                tmp = nums[i] + nums[j] + nums[k]
                if isPrime(tmp) == True:
                    answer += 1
    return answer

문제풀이

---

전달받은 정수 배열을 조합하여 소수가 되는 경우의 수를 구하면 된다.

파이썬에서는 위 문제와 같은 경우 편하게 사용이 가능한 combinations 라는 조합 모듈을 제공하나 전달받은 정수 배열에서 3개의 정수의 조합을 3중 for문으로 구현할 수 있었기 떄문에 이번 문제에서는 이를 사용하지 않고 풀었다.

문제의 핵심은 소수 판별이다. 따라서 전달받은 정수를 기반으로 소수를 판별해주는 함수를 정의한다.

소수란, 1과 자기 자신으로만 나누어지는 정수를 의미한다.

소수 판별 함수를 정의한 뒤, 3중 포문으로 전체 경우의 수를 탐색하며 각 반복에 따라 뽑아낸 3개의 정수의 합이 소수인지 아닌지 판별하여 answer값을 증가시킨다.

이후 answer를 반환한다.

다른 사람의 풀이

---

앞서 언급한 combinations 를 활용한 문제 풀이 기법을 살펴보도록 한다.

def solution(numbs):
    from itertools import combinations as cb
    answer = 0
    for a in cb(nums, 3):
        tmp = sum(a)
        for j in range(2, tmp):
            if tmp % j == 0:
                break
        else:
            answer += 1
    return answer

위 문제 풀이방법에서는 combinations를 이용해 3개의 정수를 조합하여 만들어 낼 수 있는 경우의 수를 모두 만들고 이를 각각 순회하였다.

또한, 여기서 정말 중요한 구문 중 하나인 for~else 문 이 사용되었다.

for~else문은 for문 반복이 정상적으로 종료되면 else문을 실행시킨다.

따라서, 2부터 뽑아낸 3개 정수의 합까지 반복하며 나누어 떨어지는지 확인한다.

만일 나누어 떨이지지 않는다면, 즉 소수라면 answer를 1 증가시킨다.