문제 요약
한자리 숫자가 적힌 종이 조각이 흩어져있다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 한다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇개인지 return 하도록 solution 함수를 완성하라.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0 ~ 9까지 숫자만으로 이루어져 있습니다.
- "013"은 0,1,3 숫자가 적힌 종이 조각이 흩어져 있다는 의미입니다.
입출력 예시
| numbers | return |
|---|---|
| "17" | 3 |
| "011" | 2 |
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
[0,1,1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
풀이 과정
문제를 풀기전 우선 문자열로 들어오는 numbers를 하나씩 잘라서 배열을 만들고 그 배열에서 나올수 있는 모든 조합을 구한다음, 그 조합을 담고 있는 배열을 순회하면서 소수인지 확인한고 소수의 갯수를 리턴하면 될 것이라 생각했다.
종이 조각을 하나만 사용할 수도 있고 numbers의 길이 만큼 자릿수를 만들 수 있기 때문에
"123"일 경우, [1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321] 총 15가지의 조합이 가능하다.
따라서 이렇게 조합을 만드는 로직을 만들어야 하는데, 재귀함수를 사용해서 풀어야 하는 것과 위에서 나열한 것처럼 1뒤에 나머지 올 수 있는 숫자 2, 3 3, 2를 반복하고 길이가 길어질 수록 더 반복하면 될것이라 생각했지만 구현할 수 없어서 결국 다른 사람의 코드를 검색해서 사용했다.
출처: 나만의 기록들
const getPermutations = (arr, num) => {
const results = [];
if(num === 1) return arr.map(v =>[v]);
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
const permutations = getPermutations(rest, num - 1);
const attached = permutations.map(v => [fixed, ...v]);
results.push(...attached);
})
return results;
}
const getAllPermutations = (arr) => {
let results = [];
arr.forEach(_, index, origin) => {
results.push(...getPermutations(origin, index + 1));
});
return results;
}getAllPermutations 함수를 실행하면 getPermutations 함수를 재귀적으로 실행해서 결과를 구한다. 여기서 매개변수로 전달받는 arr는 사용할 수 있는 숫자들을 담고 있고 num은 구하려는 자릿수를 나타낸다.
arr를 forEach로 순회하면서 현재 값은 fixed로 고정하고,slice를 사용해서 현재 값을 제외한 나머지 값들을 rest 배열에 넣는다. 그리고 다시 getPermutations 함수를 반복한다.
혼자서 생각해보고 문제를 완성했어야 했는데, 이것 때문에 너무 많은 시간을 소비한거 같아서 결국 다른 사람의 코드를 사용했지만 다른 사람의 코드를 보면서 내가 생각했던데로 구현을 할 수 있었다는걸 알게 되었고 정말로 막힐 경우에는 다른 사람의 코드를 찾아보되 꼭 이해하고 사용해야겠다.
여기서 문제가 끝난 것은 아니다. 우선 number는 string 이기 때문에 하나씩 잘라야 하며, 숫자로 변환된 값을 사용해야 한다. 또한 [1, 7] 처럼 만드는 것이 아니라 [17]로 만들어야 한다.
그리고 문제에 나와 있듯이 [017][17] 모두 같은 것이기 때문에 중복을 제거해야 한다.
그리고 나서 소수 판별을 해야하는데, 처음에 몰라서 문제가 됬던게 2 이상의 숫자부터 소수 판별을 해야 한다는 것이다.
function solution(numbers) {
const nums = getAllPermutations(number.split(""));
const numberArr = nums.map((n) => {
if(n.length > 1) {
return Number(n.join(""));
} else {
return Number(n);
}
})
const set = new Set(numberArr);
let count = 0;
set.forEach((n) => {
if(n < 2) return false;
for(let i = 2; i * i <= n; i++) {
if(n % i === 0) {
return false;
}
}
count++;
});
return count;
}nums에는 getAllPermutations를 실행한 결과가 들어가 있다. 아직 ['1', '7']과 같은 상태이며 2자릿수 이상일 경우에는 join을 사용해서 ['17']로 만들어 준 다음 Number를 통해 숫자로 변환한다. numberArr에는 변환된 값들이 저장되어 있다.
아직 중복이 들어있는 상태이기 때문에 Set을 사용해서 중복을 제거한다. 그 다음 set에서 forEach로 반복해 소수를 찾는다. 소수가 아닐 경우에는 false를 리턴하지만 소수 일 경우 count를 증가시킨다.
마무리
도저히 생각이 안나서 한 3일 정도는 계속 고민했던거 같다. 다른 문제도 풀어보고 여러가지 해결 방법을 시도해봤지만 결국 성공하지 못했다. 자신감도 많이 떨어졌고 다른 사람의 코드를 그대로 쓴다는 것도 부끄럽게 생각되었다. 그러다 계속 풀지 못한채 모르고 지나갈 바에 답지를 보고 이해라도 해보자는 심정으로 다른 사람의 코드를 찾아보게 되었다. 혼자서 풀지는 못했지만 이해하고 넘어갈 수 있어서 다행이라 생각한다.
