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

문제 이해하기

양의 정수 n을 k진수로 변환했을 때, 변환된 수 안에서 특정 조건에 맞는 소수의 개수를 찾는 문제입니다.

조건

• 0P0: 소수 양쪽에 0이 있는 경우
• P0: 소수 오른쪽에만 0이 있는 경우
• 0P: 소수 왼쪽에만 0이 있는 경우
• P: 소수 양쪽에 아무것도 없는 경우

단, P는 각 자릿수에 0을 포함하지 않는 소수여야 합니다.

예시

437674을 3진수로 변환하면 211020101011이 되고, 여기서 찾을 수 있는 조건에 맞는 소수는:

• 211 (P0 형태)
• 2 (0P0 형태)
• 11 (0P 형태)

총 3개입니다.

접근 방법

1단계: k진수 변환

const kBaseNumber = n.toString(k);

2단계: 0으로 구분된 숫자들 추출

const numbers = kBaseNumber.split("0").filter((num) => num !== "");

이 방법이 핵심입니다 split("0")을 사용하면 모든 조건(0P0, P0, 0P, P)을 한 번에 처리할 수 있습니다.

3단계: 소수 판별

효율적인 소수 판별 알고리즘을 구현했습니다

function isPrime(num) {
  if (num < 2) return false;
  if (num === 2) return true;
  if (num % 2 === 0) return false;

  for (let i = 3; i * i <= num; i += 2) {
    if (num % i === 0) return false;
  }
  return true;
}

최종 코드

function solution(n, k) {
  // k진수로 변환
  const kBaseNumber = n.toString(k);

  // 0으로 구분된 숫자들 추출
  const numbers = kBaseNumber.split("0").filter((num) => num !== "");

  // 소수 판별 함수
  function isPrime(num) {
    if (num < 2) return false;
    if (num === 2) return true;
    if (num % 2 === 0) return false;

    for (let i = 3; i * i <= num; i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  }

  // 각 숫자가 소수인지 확인
  let count = 0;
  for (const numStr of numbers) {
    const num = parseInt(numStr, 10);
    if (isPrime(num)) {
      count++;
    }
  }

  return count;
}

테스트 케이스 검증

// 기본 테스트 케이스
console.log(solution(437674, 3)); // 3
console.log(solution(110011, 10)); // 2

// 추가 테스트 케이스
console.log(solution(3, 2)); // 1 ("11" -> 11은 소수)
console.log(solution(5, 2)); // 0 ("101" -> 1은 소수가 아님)
console.log(solution(11, 2)); // 1 ("1011" -> 11은 소수)

핵심 인사이트

왜 split("0")이 모든 조건을 처리할 수 있을까?

문제에서 요구하는 4가지 조건을 다시 보면:

• 0P0: split("0") → ["", "P", ""] → P 추출
• P0: split("0") → ["P", ""] → P 추출
• 0P: split("0") → ["", "P"] → P 추출
• P: split("0") → ["P"] → P 추출

모든 경우에서 0으로 구분된 부분들 중에서 빈 문자열이 아닌 것들이 바로 P입니다.

시간복잡도 분석

• 시간복잡도: O(m × √M)
  • m: 추출된 숫자 개수
  • M: 가장 큰 숫자
• 공간복잡도: O(m)