https://school.programmers.co.kr/learn/courses/30/lessons/42839
1) 풀이
소수 찾는 알고리즘 + dfs로 순열 풀듯이 푸는 방식을 사용했다
소수 찾는 알고리즘은 이전에 풀어본 적이 있었고 순열 풀이도 예전 휴학때 해본 적 있으나 잊고 살다가
코테 준비한다고 급하게 풀어보는 중..
나중에 참고하려고 참고했던 자료를 첨부한다
자료 보면 풀이 이해가기 때문에 따로 적지는 않음!
2) 최종 소스코드
function solution(numbers) {
let answer = 0;
const done = [];
const arr = [...numbers];
const select = Array.from({ length: arr.length }, () => false);
function prime(k) {
if (done.includes(k) || k === 0 || k === 1) return;
for (let i = 2; i * i <= k; i++) {
if (k % i === 0) return;
}
answer++;
done.push(k);
}
function dfs(count, n) {
prime(Number(n));
if (count >= arr.length) return;
for (let i = 0; i < arr.length; i++) {
if (select[i]) continue;
select[i] = true;
dfs(count + 1, n + arr[i]);
select[i] = false;
}
}
dfs(0, "");
return answer;
}
3) 참고자료
https://rimkongs.tistory.com/115
https://myjamong.tistory.com/139
728x90
'Problem Solving > 프로그래머스' 카테고리의 다른 글
[프로그래머스/JavaScript] 아이템 줍기 (2) | 2023.04.20 |
---|---|
[프로그래머스/JavaScript] 최고의 집합 (0) | 2023.04.06 |
[프로그래머스/JavaScript] 최소직사각형 (0) | 2022.12.14 |
[프로그래머스/JavaScript] 베스트앨범 (0) | 2022.12.14 |
[프로그래머스/JavaScript] 타겟 넘버 (1) | 2022.12.14 |