69.md

k진수에서 소수 개수 구하기

문제는 정규표현식!

Try1

첫번째 시도의 코드는 아래와 같다. 여기서 포인트는 1)각각의 패턴에 맞는 숫자를 찾는 것과 2)이것이 소수인지 여부를 판단하는 것이다.

1. 패턴에 맞는 숫자를 찾는 것은 다양한 방법들이 있을 수 있다. split을 이용한 방법들도 많은 것 같은데, 나는 정규표현식을 이용하였다. 개인적으로 정규표현식이랑 안친해서 사용안하는 편인데, 이 문제는 사용하면 좋을 것 같다는 확신이 들었다. 그리고 여기서 한가지 포인트가 더 있다. 4가지 패턴(0P0, P0, 0P, P) 는 마치 집합과 같다. 아래 이미지처럼 구성되어있다. 그래서 0P0패턴으로 구한 수는 어디선가 같은 숫자를 구하게 된 것이라고 추론할 수 있다.

   

   그래서 결국, P0패턴 개수 + 0P패턴 개수 - 0P0 패턴 개수 + P패턴 개수 이런 로직을 구현하게 되었다.

2. 소수를 구하는 방법은 사실 여러가지가 있지만 그 중에서 제곱수까지만 반복하여 확인하는 방법으로 구현하였다. 만약에 여기서 시간초과가 걸린다면, 에라토스테네스의 체와 같은 알고리즘을 좀 더 도입해야 할 것이다라는 생각 정도를 하고 있었다.

function solution(n, k) {
  const converted = n.toString(k);
  const sideZero = new Set(
    converted.match(/0[1-9]*0/g)?.map((s) => Number(s.slice(1, -1)))
  );
  const rightZero =
    converted.match(/[1-9]*0/g)?.map((s) => Number(s.slice(0, -1))) || [];
  const leftZero = converted.match(/0[1-9]*/g)?.map((s) => Number(s)) || [];
  const noZero =
    converted.match(/^[1-9][1-9]*[1-9]$/g)?.map((s) => Number(s)) || [];

  const result = [...rightZero, ...leftZero, ...noZero];
  const set = new Set();
  let count = 0;
  for (let num of result) {
    if (sideZero.has(num)) {
      sideZero.delete(num);
      continue;
    }
    if (set.has(num)) count++;
    else {
      if (num > 1 && isPrime(num)) {
        set.add(num);
        count++;
      }
    }
  }

  return count;
}

function isPrime(num) {
  let count = 1;
  for (let i = 1; i <= Math.sqrt(num); i++) {
    if (num % i === 0) count++;
  }

  return count === 2;
}

그런데...시간 초과 그런 것도 아니고 그냥 틀렸다. 그런데 오류가 발생한 테스트 케이스는 대부분의 유저들에게선 오류가 나지않는 모양이였다. 그 부분에 대한 질문은 없었다. 쭈루룩 4~5개정도가 오류가 나는것으로 보아, 어디 부분에서 예외 케이스를 못잡은 것 같았다.

정규표현식 정리!

여기를 참고하여 가장 중요한 부분만을 정리해본다. 요새는 GPT친구한테 물어보면 알아서 다 짜주긴하던데... 그래도 개발자인 나도 잘 알아야지...암...그렇고 말고...🫠