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

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

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

 

---

풀이 과정

---

1. 우선 주어진 수를 k진수 문자열로 변환시켜 준다.
   1. k진수 문자열로 변환시키는 방법은 수가 0이 될때까지 k로 나눈 나머지를 앞에 붙여주고, 수를 k로 나누어 주는 방식으로 계산하면 된다.
   2. 2진수는 bin으로 해줄수도 있지만.. k가 3~10이니깐.. 위 방식으로 구해주는게 제일 좋을듯?
2. 구해준 2진수 문자열에서 조건에 맞는 소수를 구해준다.
   1. 결국 조건들을 보면, 숫자들이 0을 기준으로 split 된다는걸 볼 수 있다.
   2. 이 때, 그냥 "0" 으로 split 해준다면 문자열이 "00"같은 경우에는 빈 문자열도 등장하기 때문에, 정규 표현식을 사용해주는게 좋다. re 모듈을 사용하고, "0+"로 split 해준다
   3. split된 결과 중 소수인 개수를 구해서 리턴시켜 준다.

---

소스 코드

---

import math
import re

def convert(n, k):
    cv = ""
    while n != 0:
        cv = str(n % k) + cv
        n //= k
    
    return cv

def check_prime(n):
    if n == 1:
        return False
    
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
        
    return True

def solution(n, k):
    PATTERN = r"0+"
    answer = 0
    convert_string = convert(n, k)
    st_list = re.split(PATTERN, convert_string)
    
    for st in st_list:
        if st == "":
            continue
        if check_prime(int(st)):
            answer += 1
        
    return answer