[2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기

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

프로그래머스

 

 

1. 해결 방법

중요한 포인트는 n을 k진수로 변환하는 코드와 소수인지 아닌지 판별하는 코드이다.

1. 주어진 n을 k진수로 변환한다.
2. 변환했으면, 0 주위에 있는 숫자가 소수인지 판별해야한다.
3. 조건을 보면 그냥 0을 제외한 모든 숫자를 검사하면 된다.
4. 각 숫자가 소수인지 판별한다.
5. 소수인지 판별 할때, int(n ** 0.5)로 범위를 줄이지 않으면 1번 테스트 케이스에서 시간초과가 뜬다.;;;;;;;;

(정답코드에는 import string 막 이랬는데 뭔지 몰라서 그랬음;;)

 

 

2. 정답코드

(1) n을 k 진수로 변환 코드

def conversion(n, k):   # n을 k 진수로 변환
    arr = []
    while n!= 0:
        r = n%k
        n = n//k
        arr.append(r)
    return ''.join(list(map(str,arr[::-1])))

 

(2) 소수인지 판별하는 코드 (시간 초과 고려)

def prime_check(n):     # n이 소수인지 아닌지 판별
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

 

(3) 정답코드

import string

tmp = string.digits+string.ascii_lowercase
def convert(num, base) :
    q, r = divmod(num, base)
    if q == 0 :
        return tmp[r] 
    else :
        return convert(q, base) + tmp[r]
    
def div_number(num):
    if num == 2:
        return True
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        else:
            return True
    
    
def solution(n, k):
    answer = 0
    
    s = list(convert(n, k).split('0'))
    for num in s:
        if num == '' or int(num) == 1:
            continue
        
        if div_number(int(num)) == True:
            answer += 1

            
    return answer