[프로그래머스] Lv2 - K진수에서 소수 개수 구하기

2022 KAKAO BLIND RECRUITMENT

• Lv 2. K진수에서 소수 개수 구하기 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/92335

Code

import math

# n을 k 진수로 변환하는 함수
def get_num(n, k):
    num = ''
    while n > 0:
        n, mod = divmod(n, k)
        num += str(mod)
    return num[::-1]

# 소수인지 확인하는 함수
def check_prime(num):
    if num == 1:
        return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def solution(n, k):
    answer = 0

    # k 진수 변환 -> 조건에 맞는 소수 개수 구하기

    # k 진수 변환
    num = get_num(n, k)
    print(num)

    # 조건에 맞는 소수 확인
    num_check = num.split("0")
    for i in range(len(num_check)):
        if(num_check[i] != '' and check_prime(int(num_check[i]))):
            answer += 1

    return answer

풀이 및 해설

• k진수 변환 → 0으로 split했을 때 남아있는 숫자들을 하나하나 소수인지 확인 → 소수라면 answer ++
• 시간 초과를 해결하기 위해서 소수를 판별할 때 제곱근으로 판별해서 시간복잡도를 줄여야 했다.
• ⭐️ n을 k진수로 변환하는 함수에서 divmod를 사용하면 간단하게 변환할 수 있다 !! 외워둬야지 ⭐️

What I learned

divmod(x, y)

• x를 y로 나눈 몫과 나머지를 튜플 형태로 반환

divmod(x, y) = (x // y, x % y)

k진수 변환하기

• divmod를 사용해서 몫을 반복문을 통해 계속 n으로 나눠주는 값을 문자열 형태로 붙인 뒤 뒤집기

# n을 k 진수로 변환하는 함수
def get_num(n, k):
    num = ''
    while n > 0:
        n, mod = divmod(n, k)
        num += str(mod)
    return num[::-1]