[JavaScript] k진수에서 소수 개수 구하기

k진수에서 소수 개수 구하기 - 프로그래머스

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

 

문제 복기

1월 5일에 풀고, 한 달이 지나서야 풀이를 남기게 되어서 정확한 맥락을 놓쳤을 수도 있기 때문에

최대한 꼼꼼히 다시 보고, 저의 그 당시 생각들을 떠올려가며 정리해보겠습니다.

 

문제를 읽어보시면 아시겠지만, 

 

문제 조건

 

문제 조건 아래 바로, 아래의 예시가 나옵니다.

위의 조건에 맞는 소수는 211, 2, 11로 총 3개가 됩니다. 

 

마지막 조건과 위의 예시를 잘 읽고 생각하면, 

결국은 0을 기준으로 모두 분리해줘야 한다는 사실을 알게 되었습니다.

 

 

문제 풀이

1. toString()의 인자로 k를 넣어주어, k진수 문자열로 변환했습니다.

2. 0을 기준으로 모두 split 했습니다.

3. 소수를 판별하는 로직을 추가했습니다. 

 

(다들 아실 수도 있지만, 소수를 판별하는 로직을 구현할 때는 중복으로 검사하는 횟수를 줄이기 위해서 Math.sqrt를 사용하는 방식으로 진행해야 대개의 경우 시간초과를 피할 수 있습니다.)

 

4. primeArr에는 소수인지 아닌지 판별한 값들을 모두 담습니다. ex) 211, 2, 1, 1, 11 -> [ true, true, false, false, true ]

5. filteredArr에는 최종적으로 true인 값들만 담고, 길이를 반환합니다.

 

function solution(n, k) {
  const convertedStr = n.toString(k);
  
  const sliceOfZero = convertedStr.split("0");
  
  const isPrimeNumber = (n) => {
    let cnt = 0;
    if (n < 2) return false;
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i === 0) cnt++;
    }
    return cnt === 0;
  };
  
  const primeArr = sliceOfZero.map((e) => isPrimeNumber(e));
  
  const filteredArr = primeArr.filter((e) => e === true);
  
  return filteredArr.length;
}