문제 요구사항
프로그래머스 재귀 문제 Lv.1 소수 만들기
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.
숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
- nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
입출력 예
|
nums
|
return
|
|
[1,2,3,4]
|
1
|
|
[1,2,7,6,4]
|
4
|
성공 코드
보통 3중 for문을 이용해서 푸는데, 그 방법 보다는 재귀로 풀고싶어서 여러 가지 시도를 해보았다.
도저히 재귀로 풀 방법이 생각나지 않아서 GPT의 도움을 받아서 풀었다.
코드별 설명
1. 주어진 숫자가 소수인지 아닌지 구하는 함수
function isPrime(num) {
if (num <= 1) return false;
for (let i = 2; i * i <= num; i++) {
if (num % i === 0) return false;
}
return true;
}약수에는 짝이 있기 때문에, 특정 수의 제곱이 num보다 작을 때까지 비교하며 특정 수가 약수인지 아닌지 찾는다.
Ex) 64 -> 64의 약수는 1 x 64, 2 x 32, 8 x 8 이므로 32까지 가지 않아도 2에서 약수가 있음이 검출된다.
2. 재귀 함수
// 조합을 재귀적으로 생성하고, 그 합이 소수인 경우를 계산하는 함수
function findCombinations(index, selected, sum) {
if (selected.length === 3) {
if (isPrime(sum)) count++;
return;
}
// 현재 전달 받은 index + 1, 현재 전달받은 배열에 현재 인덱스 값 추가해서 함수 호출
// 전달한 배열의 길이가 3이면 return 되어 i가 더해짐
for (let i = index; i < nums.length; i++) {
findCombinations(i + 1, [...selected, nums[i]], sum + nums[i]);
}
}index, selected, sum 세 개의 매개변수를 갖는다.
index -> 전체 nums의 인덱스 중 현재 가르키고 있는 인덱스
seleted -> 선택된 숫자들이 들어있는 배열
sum -> seleted 배열에 있는 숫자들의 합
seleted 안에 숫자가 3개라면 3개 숫자 합이 소수인지 아닌지 판별한다.
안에 들어있는 숫자가 3개가 아니라면, 다음 인덱스의 값을 추가하여 또 다시 함수를 호출한다.
이를 그림으로 정리해보면 아래 그림과 같다.
전체 코드
function solution(nums) {
let count = 0;
// 주어진 수가 소수인지 판별하는 함수
function isPrime(num) {
if (num <= 1) return false;
for (let i = 2; i * i <= num; i++) {
if (num % i === 0) return false;
}
return true;
}
// 조합을 재귀적으로 생성하고, 그 합이 소수인 경우를 계산하는 함수
function findCombinations(index, selected, sum) {
if (selected.length === 3) {
if (isPrime(sum)) count++;
return;
}
// 현재 전달 받은 index + 1, 현재 전달받은 배열에 현재 인덱스 값 추가해서 함수 호출
// 전달한 배열의 길이가 3이면 return 되어 i가 더해짐
for (let i = index; i < nums.length; i++) {
findCombinations(i + 1, [...selected, nums[i]], sum + nums[i]);
}
}
// 첫 번째 인덱스부터 조합 생성 시작
findCombinations(0, [], 0);
return count;
}재귀를 생각해내기가 어려운 문제인 것 같다.
이해하고 나면 그렇게 어려운 알고리즘은 아니지만, 인적 사고로 바로 생각해내기에는 복잡함이 있다.
또한, 오히려 재귀를 쓰면 시간 초과가 되는 문제들이 있기 때문에 주어진 문제에 맞추어 알고리즘을 잘 선택해야할 것 같다.
특히, 프로그래머스의 모음 사전과 같은 문제는 재귀를 사용하기가 더욱 어려운 문제였고,
피보나치 수 문제는 재귀를 사용하면 시간 초과, for문을 사용해야 통과되는 경우가 있었다.
'CodingTest > Javascript' 카테고리의 다른 글
| [JavaScript] 백준 DP 문제 : 11053번 가장 긴 증가하는 부분 수열 (0) | 2024.05.13 |
|---|---|
| [JavaScript] 백준 DP 문제 : 1309번 동물원 (1) | 2024.05.13 |
| [JavaScript] 프로그래머스 Greedy 문제 : 큰 수 만들기 (0) | 2024.05.11 |
| [JavaScript] 프로그래머스 정렬 문제 : H-Index (0) | 2024.05.10 |
| [JavaScript] 백준 28279번 덱2 (0) | 2024.05.10 |
