소수 찾기

소수 찾기

2020.07.30

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과 재귀를 이용해서 풀었는데 그중에서도 좋아요를 가장 많이 받은 사람의 풀이는 압도적으로 효율성이 높았다;;

• 결국 모든 경우의 수를 구현하는 알고리즘을 이해해야 하는 것 같은데 지금의 나에게는 무리인 것 같다 ㅠㅠ