const isPrimeNumber = (num) => {
if (num <= 1) {
return false;
}
if (num <= 3) {
return true;
}
if (num % 2 == 0 || num % 3 == 0) {
return false;
}
for (let i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
};
const initHash = (arr) => {
const hash = {};
for (const el of arr) {
if (!hash.hasOwnProperty(el)) {
hash[el] = 1;
} else {
hash[el]++;
}
}
return hash;
};
const isInNumbers = (num, hash) => {
const arrOfNum = num.toString().split("");
const limit = arrOfNum.length;
for (let i = 0; i < limit; i++) {
const current = arrOfNum[i];
if (!hash.hasOwnProperty(current)) {
return false;
}
hash[current]--;
if (hash[current] < 0) {
return false;
}
}
return true;
};
const solution = (numbers) => {
const maxIdx = numbers
.split("")
.map((char) => parseInt(char))
.sort((a, b) => b - a)
.join("");
const arrOfInput = numbers.split("");
const result = [];
for (let i = maxIdx; i >= 2; i--) {
if (isPrimeNumber(i) && isInNumbers(i, initHash(arrOfInput))) {
result.push(i);
}
}
return result.length;
};
심각하게 비효율적인 풀이 결과가 나왔다.
numbers로 구성 가능한 경우의 수를 모두 구현하는 방법을 알지 못해 최대값을 구한 뒤 1까지 내려가면서 하나하나 조건 검사하는 방법을 선택한 게 잘못인 것 같다.
문제는 다른 사람의 풀이를 봐도 모르겠다는 것...
다들 set과 재귀를 이용해서 풀었는데 그중에서도 좋아요를 가장 많이 받은 사람의 풀이는 압도적으로 효율성이 높았다;;
결국 모든 경우의 수를 구현하는 알고리즘을 이해해야 하는 것 같은데 지금의 나에게는 무리인 것 같다 ㅠㅠ