[카카오 코테 2022 | python] k진수에서 소수 개수 구하기

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92335
• level2
• 2022 KAKAO BLIND RECRUITMENT

 

Q1) 문제를 어떻게 이해하셨나요?
A1) 이 문제는 양의 정수 n을 k진수로 바꾼 후, 그 안에 0을 기준으로 나뉜 연속된 숫자들 중 소수인 수의 개수를 구하는 문제입니다. 여기서 주의할 점은, 10진수로 해석해서 소수인지 판단해야 한다는 점입니다.

Q2) 풀이 계획
A2) 먼저 n을 k진수 문자열로 변환합니다. 변환된 문자열을 '0'을 기준으로 분할합니다. 각 토큰에 대해 비어 있지 않고 10진수로 변환했을 때 소수이면 결과에 포함시킵니다. 최종적으로 소수 개수를 리턴합니다.

 

💡 최적화된 코드

# k진수는 숫자를 k개의 숫자(기호)를 사용해 표현하는 방식
def to_k_base(n, k):
    result = ''
    while n > 0:
        result = str(n % k) + result # 가장 낮은 자리수부터
        n //= k
    return result

# 소수는 1과 자기 자신만을 약수로 가지는 자연수
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1): # 약수는 √n을 기준으로 대칭이기 때문에
        if n % i == 0:
            return False
    return True

def solution(n, k):
    k_base = to_k_base(n, k)
    parts = k_base.split('0')
    
    result = 0
    for p in parts:
        if p == '':
            continue
        if is_prime(int(p)):
            result += 1
    return result

 

✅ 내장함수

bin(10)  # 2진수 '0b1010'
oct(10)  # 8진수 '0o12'
hex(255)  # 16진수 '0xff'

# 역변환
int('1010', 2) # 10
int('12', 8) # 10
int('ff', 16) # 255