[코딩테스트] 2022 KAKAO BLIND RECRUITMENT- k진수에서 소수 개수 구하기

---

문제

 

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

프로그래머스

 

어떤 수 n을 k진수로 변환한 뒤, 0을 제외한 나머지 묶음들 중에 소수의 개수가 몇 개인지 구하는 문제.

 

 

 

---

전략

 

01. k진수 변환, 소수

 

 문제를 보고 두 가지 함수가 추가로 필요할 것 같았다. 먼저 임의의 n을 k진수로 변환하는 함수, 그리고 0을 제외하고 유효한 값이 소수인지 아닌지 판별하는 함수.

 

 

 

---

풀이

 

import re

def custom_digit_change(n, k):
    r_str = ''
    
    while n > 0:
        cache = n % k
        n = n // k
        r_str += str(cache)
    
    return r_str[::-1]

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

def solution(n, k):
    custom_dn = custom_digit_change(n, k)
    num_list = re.findall("[1-9]+", custom_dn)
    result = 0
    
    for i in num_list:
        if check_prime_number(int(i)):
            result += 1
    
    return result

 

 먼저 진수 변환을 실행해 그 값을 문자열로 리턴하는 custom_digit_change함수를 만들었다.

 

def custom_digit_change(n, k):
    r_str = ''
    
    while n > 0:
        cache = n % k
        n = n // k
        r_str += str(cache)
    
    return r_str[::-1]

 

 while문 안에서 n이 0이 될 때까지 반복하는데, 첫번째로 얻은 cache값은 가장 작은 자리수가 되고 n를 k로 나눈 몫에서 한번 더 나머지를 구하면 그 다음 작은 자리수가 된다. 이를 반복하면 가장 작은 자리수부터 시작하는 r_str 문자열을 얻을 수 있으므로 return에서 r_str[::-1]로 순서를 뒤집어서 반환하면 k진수로 변환할 수 있다.

 

 

custom_dn = custom_digit_change(n, k)
    num_list = re.findall("[1-9]+", custom_dn)

 

 그 다음으로는 리턴받은 결과를 custom_dn에 저장하고 re모듈의 findall함수를 이용해 0을 제외한 나머지 문자열의 묶음으로 리스트를 만들었다. 정규표현식 부분을 보면 0을 제외하고 1-9사이의 값이 1 이상인 구간만을 묶을 수 있도록 "[1-9]+"로 만들어 주었다.

 

 이제 이 리스트의 각 요소들이 소수인지 아닌지 판별하기 위해 check_prime_number함수를 만들어 주었다.

 

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

 

 함수 호출할 때 인자 자체에 int()로 형변환을 해주어 함수 안에서는 정수형태의 값으로 활용할 수 있게 했다. num이 1일 경우 소수가 아니므로 제외해주고, 2 이상에서는 에라스토네테스의 체 원리를 이용해 num의 제곱근까지 반복하면서 나머지가 0일 경우 소수가 아님을 판정해주었다. 만약 이 검사를 통과하면 True, 즉 소수로 판정해주었다.

 

 이제 이 결과를 반복하면서 소수의 개수를 구해주면 된다.