[프로그래머스 | Python] k진수에서 소수 개수 구하기 (카카오 블라인드 2022)

[Level 2] k진수에서 소수 개수 구하기 - 92335

문제 링크

구분

코딩테스트 연습 > 카카오 2022 블라인드

풀이 요약

진법 변환과 소수 판별을 요구하는 구현 문제. 소수 판별에서 n보다 작은 모든 소수를 구하는 것이 아니라 2부터 n의 루트 사이의 범위에서 소수를 구하여야 효율성 테스트를 통과할 수 있다.

나의 풀이

import math

def convert_number(n, k):
    s = ''
    while n > k-1:
        s += str(n % k)
        n //= k
    s += str(n)
    return s[::-1]

def is_prime(n):
    if n < 2:
        return False

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

    return True


def solution(n, k):
    answer = 0
    split_list = convert_number(n,k).split('0')
    for number in split_list:
        if number.isnumeric() and is_prime(int(number)):
            answer += 1
    return answer

배운 점

소수 판별에서 판별에 필요한 필수 범위를 지정하여 계산 시간을 단축하는 법을 알게 되었다. 예를 들어, 숫자 16에 대한 약수는 1,2,4,8,16의 모양으로 대칭인 형태이므로 16의 제곱근까지의 범위 안에서 약수가 있는지 체크하는 것만으로도 n의 소수 여부를 판별할 수 있다.

문자열을 리스트로 변환하지 않고도 문자열을 뒤집는 방법에 대해서도 알게 되었다. 기존에는 문자열을 리스트로 변환해서 reverse() 함수를 이용한 뒤 ''.join() 함수로 다시 문자열로 변환 해주었는데, s[::-1]를 이용하면 자료형 변환이 필요없어서 편리했다. 문자열 슬라이싱에서 문자열[시작:끝:규칙]이라는 규칙이 있는데, 규칙에 -1을 넣어주게 되면 뒤에서부터 한 요소씩 잘라서 문자열을 만들어준다.

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

입출력 예