문제 설명

문제 출처

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

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

제한 사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.

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

예제 입출력

Solution

전형적인 조합(Combination) 문제이다. 조금 다른 것이 있다면 소수 판별 로직이 추가된다는 점이다.

소수 판별 역시 수학 문제로 자주 등장하는 문제이기 때문에 한 번 로직을 이해하고 파악해두면 두고두고 쓸 만 하다.

1. 소수 판별

소수 문제가 등장할 때 주로 사용되어지는 방법은 바로 에라토스테네스의 체이다. 하지만 이번 문제에는 적합하지 않다.

그 이유는 에라토스테네스의 체는 이름에서 알 수 있듯 어떤 범위 내의 연속된 숫자 집합(예를들면 1 ~ 100)에서 소수인 것 만 골라내는 알고리즘 으로써, 우리가 필요한 것은 범위 내의 숫자 중 소수를 판별하는 것이 아니라 숫자 3개의 합이 소수인지를 판별하는 것이기 때문에 독립적인 숫자 소수 판별을 진행한다.

독립적인 숫자의 소수 판별은 수학적인 지식이 충분하지 못해 검색을 통해서 확인했다.

어떤 수가 소수인지를 판별할 때 \(2 < i<=\sqrt{checkNum}\) 범위의 i가 checkNum으로 나누어 떨어지지 않는다면 checkNum은 소수이다.

이를 이용하여 checkNum이 소수를 판별하려는 수 (3개 수의 합)이라 하면 쉽게 계산 가능하다.

1. 조합

주어진 배열(nums)에서 3개의 숫자들을 선택하는 것은 조합이다. 조합 식은 앞서 말한 것 처럼 선택하려는 요소의 개수 만큼 루프를 이용해서 해결할 수 있다.

하지만 나는 재귀 성애자이기 때문에 재귀를 이용하여 문제를 풀었다. 이를 이용하면 요소의 개수가 몇 개든간에 (다중 루프에 비해)소스코드를 변경하지 않고 사용 가능하다.

간단히 로직을 설명하자면 현재까지 더해진 요소의 개수가 주어진 요소의 개수(여기서는 3개)와 동일할 때 까지 재귀적으로 요소를 선택하게끔 구현하였다.

Code

몇줄 평

1. 소수 판별의 로직이 신선했다. 제곱근 계산을 위해 Math API를 사용하지 않고 i*i<=checkNum 표현으로 제곱근 계산을 표현. 사실 수학적으로는 너무나 당연.

2. 재귀적인 접근

참고 및 출처