[프로그래머스] 소수 찾기 JavaScript
완전 탐색 문제마다 매일 막히는 것 같아서 완전 탐색 문제들에 좀 더 익숙해지기 위해서 완전 탐색 카테고리를 풀어봤다. Level 2인데도 불구하고 생각해내는 데 오래 걸려서 좀 많이 슬펐다..
이 문제에서는 수를 조합해서, 그 숫자가 소수인지를 판별해야한다. 그러기 위해서 필요한 것을 정리해봤다.
- 한 자리 숫자를 조합해 여러 자리 숫자를 만드는 기능
- 만들어진 숫자가 소수인지 판별하는 기능
소수 판별은 꽤나 자주 만날 수 있는 문제이기 때문에, 어렵지 않게 만들어낼 수 있다. 하지만 한 자리 숫자를 조합해서 여러 자리 숫자를 어떻게 만들어야할지 좀처럼 잘 방법이 떠오르지 않았다.
풀이
여러 개의 숫자를 조합하고 소수 판별을 하기 위해서 일단 for문을 통해서 어떻게 만들어낼 수 있을지 생각해봤다.
예를 들어 [1, 7]이 주어졌다면 아래와 같이 동작하면서 답을 찾아야 할 것이다.
- 1이 소수인지 판별
- 17을 만들어서 소수인지 판별
- 7이 소수인지 판별
- 71이 소수인지 판별
그런데 문제는 총 몇자리가 주어질지 모르기 때문에, 중첩 포문으로 만들기엔 무리가 있을 것 같아서 일단 for문으로 위 상황에 대해 만들어 본 다음에 재귀로 바꿔보았다. (아직도 재귀는 바로 생각해내기 너무 어렵다..😥)
그래서 구현한 재귀 함수는 findPrimeNumbers()
인데, 자신에 대한 소수 판별을 한 뒤 자기 자신을 제외한 배열과, 앞자리에 붙어야할 값(자기 자신)을 다음 함수로 넘겨서 한자리씩 더해가면서 체크하는 방식이다.
여기서 중복된 소수들이 들어가는 것은 따로 체크하지 않았는데, Set을 활용해서 마지막에 중복된 숫자들을 없앤 배열을 만들고 그 길이를 return 하도록 했다.
코드
JavaScript
function solution(numbers) {
const numberList = numbers.split('');
const answers = findPrimeNumbers(numberList);
return [...new Set(answers)].length;
}
function findPrimeNumbers(numberList, prevNumber) {
const frontPaddingNumber = prevNumber || '';
return numberList.reduce((primeNumbers, number, index) => {
if (isPrimeNumber(Number(frontPaddingNumber + number))) {
primeNumbers.push(Number(frontPaddingNumber + number));
}
const nextNumberList = [...numberList];
nextNumberList.splice(index, 1);
const result = findPrimeNumbers(
nextNumberList,
frontPaddingNumber + number,
);
primeNumbers.push(...result);
return primeNumbers;
}, []);
}
function isPrimeNumber(number) {
const notPrime = [0, 1];
if (notPrime.includes(number)) return false;
for (let i = 2; i * i <= number; i++) {
if (number % i === 0) return false;
}
return true;
}