Level 2 210921 https://programmers.co.kr/learn/courses/30/lessons/42839
과거 내 풀이
function primality(n) {
let i = 2;
if (n <= 1) return false;
if (n === 2) return true;
while (i * i <= n) {
if (n % i === 0) {
return false;
}
i += 1;
}
return true;
}
const getPermutations = (arr, selectNum) => {
const res = [];
if (selectNum === 1) return arr.map((item) => [item]);
arr.forEach((fixed, idx, org) => {
const rest = [...org.slice(0, idx), ...org.slice(idx + 1)];
const permutations = getPermutations(rest, selectNum - 1);
const combAttaced = permutations.map((perm) =>
[fixed, ...perm].join("")
);
res.push(...combAttaced);
});
return res;
};
function solution(numbers) {
var answer = 0;
let list = [];
for (let i = 1; i < numbers.length + 1; i++) {
getPermutations(numbers.split(""), i).forEach(
(item) => primality(Number(item)) && list.push(Number(item))
);
}
const set = new Set(list);
const uniqueArr = [...set];
answer = uniqueArr.length;
return answer;
}
test("solution", () => {
// expect(solution([3, 0, 6, 1, 5])).toBe(3);
// expect(solution([88, 89])).toBe(2);
// expect(solution([3])).toBe(1);
// expect(solution([1])).toBe(1);
expect(solution([0])).toBe(0);
expect(solution([0, 0, 0])).toBe(0);
});문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
입출력 예 설명
예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
My solution
먼저 소수가 되는 조건을 알고 있어야 한다. 내가 기존에 사용한 방식은 일일이 나누어주는 것이다.
function primality(n) {
let i = 2;
if (n <= 1) return false;
if (n === 2) return true;
while (i * i <= n) {
if (n % i === 0) {
return false;
}
i += 1;
}
return true;
}위 방식은 기본적으로 시간복잡도가 O(n)이다.
하지만 소수를 찾을 때 제곱근을 이용해 반만 검사해도 소수 판별이 가능하다. 에라토스테네스의 체라고도 한다. (1을 제외하고 2부터 N까지 자신을 제외하고 순차적으로 자신의 배수들을 지워가면 결국에는 소수들만 남는다는 원리이다. 여기서 N은 임의의 수이므로 √n이 되어도 결과는 같다.)
따라서 시간복잡도도 O(√n)이 된다. 아래의 함수를 사용하였다.
function isPrime(num) {
if(n <= 1) return false;
if(num === 2) return true;
for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
if(num % i === 0){
// 한 번이라도 나누어 졌으니 소수가 아니므로 return false
return false;
}
}
// 나눠진 수가 없다면 해당 수는 소수이므로 return true
return true;
}기존에는 순열을 구해주는 함수를 가져와 계산했지만 완전탐색을 사용해보기 위해서 아래와 같이 DFS라는 함수를 선언했다.
이 문제에서 DFS를 이용하는 것은 순열구하기 문제와 비슷하다. 숫자가 어느 위치에 서느냐에 따라 값이 달라지기 때문에 조합을 사용하면 안된다.
ch라는 체크 배열을 두고 각 인덱스는 numbers 배열의 각 인덱스에 매칭한다. numbers 배열의 값이 사용된 경우 ch배열의 같은 인덱스에 1을 할당하도록 했다.
따라서 하나하나 사용후 체크하면서 재귀를 따라 들어가면 Level(L)이 m과 같아지는 때가 온다.
재귀에서 필수적이라는 종료 조건이다.
function DFS(L, m) {
if (L === m) { ,,,L은 0부터 시작해서 DFS를 거듭할수록 +1씩 늘어나는 구조이고 DFS에 진입하기 전에 numbers배열의 하나의 원소를 사용하는 것이므로 L은 numbers 배열에서 몇 개의 원소를 사용했는지를 의미하게 된다.
function DFS(L, m) {
,,,
else {
for (let i = 0; i < n; i++) {
// 해당 인덱스의 원소를 사용해도 된다면(0)
if (ch[i] === 0) {
ch[i] = 1;
tmp[L] = nums[i];
DFS(L + 1, m);
ch[i] = 0; // push 후 back했으면 그 가지를 사용하기로 했던 것(1)을 0으로 초기화
}
}
}과거에 정해준 숫자만큼의 순열을 만들어내는 함수를 구현한 적이 있기 때문에 이 정해진 숫자에다가 1부터 numbers의 길이까지 할당하면서 각 숫자에 맞는 순열을 만들어낼 수 있다고 생각했다.
따라서 가장 처음에는 1개의 원소만 사용한 경우의 순열을 전부 찾아내려고 했다. for문의 i를 1씩 n까지 DFS에 인자로 주기 때문에 첫번째로 호출되는 것은 DFS(0, 1)이다. 그다음은 2개 사용, 3개 사용하는 순으로 늘어난다. 이 과정 동안 조건에 맞는 값이 나온다면 answer에 포함시킨다.
tmp는 임시적으로 사용한 값들을 받아줄 배열이므로 사용할 값들의 개수가 사이즈가 된다.
,,,
for (let i = 1; i <= n; i++) {
tmp = Array.from({ length: i }, () => 0);
DFS(0, i);
}L이 원하는 원소의 개수만큼 뻗어내려갔을 때 if(L === m)의 블록 안으로 들어간다. 그 다음 tmp라는 배열에 저장된 모든 문자열 원소를 숫자로 이어붙인다. 그리고 아래와 같이 포함되지 않고(중복되지 않고) 소수인 것이면 answer에 push한다.
,,,
if (L === m) {
// 여기서 중복 걸러주는 로직 필요
const checkNum = Number(
tmp.reduce((prev, curr) => prev + curr, "")
);
if (!answer.includes(checkNum) && isPrime(checkNum))
answer.push(checkNum);
}
,,,소스 코드
function solution(numbers) {
let answer = [];
let nums = numbers.split("");
let n = nums.length;
let ch = Array.from({ length: n }, () => 0); // 해당 인덱스의 원소를 사용해도 될지 판단하는 ch 배열
let tmp;
// 재귀를 이용한 완전탐색
function DFS(L, m) {
if (L === m) {
// 여기서 중복 걸러주는 로직 필요
const checkNum = Number(
tmp.reduce((prev, curr) => prev + curr, "")
);
if (!answer.includes(checkNum) && isPrime(checkNum))
answer.push(checkNum);
} else {
for (let i = 0; i < n; i++) {
// 해당 인덱스의 원소를 사용해도 된다면(0)
if (ch[i] === 0) {
ch[i] = 1;
tmp[L] = nums[i];
DFS(L + 1, m);
ch[i] = 0; // push 후 back했으면 그 가지를 사용하기로 했던 것(1)을 0으로 초기화
}
}
}
}
for (let i = 1; i <= n; i++) {
tmp = Array.from({ length: i }, () => 0);
DFS(0, i);
}
return answer.length;
}
test("solution", () => {
// expect(solution("17")).toBe(3);
expect(solution("011")).toBe(2);
});