Younho9 NotesProgrammers 42839. 소수 찾기
Title
Programmers 42839. 소수 찾기
Category
AlgorithmTags
Aliases
Programmers 42839. 소수 찾기Created
3 years ago
Updated
last year
| 문제 유형 | 난이도 | 걸린 시간 | 해결 유무(✅/❌) |
|---|---|---|---|
| 완전탐색 | lv.2 | 2시간 | ✅ |
설계 방법
문자열 배열이 주어지면 모든 순열을 찾는 함수를 이용한다.
ex) ['0', '1', '1'] => [ '0', '1', '1', '01', '01', '10', '11', '10', '11', '011', '011', '101', '110', '101', '110' ]
모든 순열을 Number 함수로 숫자로 만든다. (이 과정에서 앞의 0이 사라진다.)
각 숫자가 소수이면 소수 Set에 추가한다. (이 과정에서 중복이 제거된다.)
코드
javascript
function solution(numbers) {
const primeNumbers = new Set();
for (let i = 1; i <= numbers.length; i++) {
getPermutation(numbers.split(''), i)
.map(Number)
.forEach((number) => {
if (isPrime(number)) {
primeNumbers.add(number);
}
});
}
return primeNumbers.size;
}
function getPermutation(arr, n) {
if (n === 1) {
return arr;
}
return arr.reduce((perms, cur, idx) => {
getPermutation(
[...arr.slice(0, idx), ...arr.slice(idx + 1)],
n - 1,
).forEach((perm) => {
perms.push(cur + perm);
});
return perms;
}, []);
}
function isPrime(num) {
if (num < 2) return false;
if (num === 2) return true;
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return true;
}
function solution(numbers) {
const primeNumbers = new Set();
for (let i = 1; i <= numbers.length; i++) {
getPermutation(numbers.split(''), i)
.map(Number)
.forEach((number) => {
if (isPrime(number)) {
primeNumbers.add(number);
}
});
}
return primeNumbers.size;
}
function getPermutation(arr, n) {
if (n === 1) {
return arr;
}
return arr.reduce((perms, cur, idx) => {
getPermutation(
[...arr.slice(0, idx), ...arr.slice(idx + 1)],
n - 1,
).forEach((perm) => {
perms.push(cur + perm);
});
return perms;
}, []);
}
function isPrime(num) {
if (num < 2) return false;
if (num === 2) return true;
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return true;
}
시간 복잡도
- 순열 : O(N!)
어려웠던 점
모든 순열 찾기, 소수 찾기, 중복 제거, 앞의 0 제거 등의 기능을 분리할지 합성할지 고민이 길어졌다.
모든 순열 찾기 함수를 작성하는데 어려움을 겪었다.
모든 순열을 검색하는 것까지 시간 복잡도를 허용할 것인지 고민을 많이 했다.
- 제한 사항을 보고 어느 정도의 시간 복잡도가 통과할 것인지가 예측 가능한지 궁금하다.
10자리 수까지 테스트 해보았는데, 반복문 안에서 재귀함수를 n 깊이만큼 들어갔다가 빠져나와서 그런지 stack overflow는 발생하지 않았다.
10자리 수 테스트가 8분 정도 걸렸다.
