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

k 진수에서 소수 개수 구하기에 대한 문제 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

n을 k 진수로 변환한 후에 0을 기준으로 정수를 분리한 뒤 해당 정수들이 소수인지 판별하는 문제입니다. 해결 순서는 다음과 같습니다.

1. n을 k 진수로 변환한다.
2. 1의 결과를 0을 기준으로 분리한 후에 number_list에 정수형으로 저장한다.
3. number_list를 순환하며 소수인지 판별한다.
4. 3의 결과가 참이라면 answer += 1을 해준다.
5. 3을 반복한다.

0을 기준으로 나누어주는 이유는 문제에서 0P, P0, 0P0(P는 0이 아닌 양의 정수)의 경우에서 P가 소수인지 판별하라고 하였기 때문입니다.

 

다음은 해결 순서를 기준으로 작성한 코드입니다.

 

def convert_by(n, mode):
  base = ''
  while n > 0:
    n, mod = divmod(n, mode)
    base += str(mod)
  return base[::-1]

def is_prime(n):
  if n < 2: return False

  for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0:
      return False
  return True

def solution(n,k):
  answer = 0
  number_list = [int(item) for item in convert_by(n, k).split('0') if item != ""]

  for number in number_list:
    if is_prime(number):
      answer += 1

  return answer

 

 

k 진수에서 소수 개수 구하기는 진법으로 변환하는 covert_by 함수를 작성할 수 있는지가 주요 포인트였던 것 같습니다.

 

소수 판별에 있어서 2부터 루트(n)까지를 나눈 나머지가 0이 아님을 확인하는 방법과 에라토스테네스의 체를 사용하는 방법이 존재하는데 위의 코드는 전자를 사용하여 문제를 해결하였습니다. 추후에 에라토스테너스의 체를 사용하여 문제를 해결하는 코드를 작성해보면 도움이 될 것 같습니다.