[Python] 프로그래머스: k진수에서 소수 개수 구하기

K진수에서 소수 개수 구하기

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

2022 KAKAO BLIND RECRUITMENT

문제 설명

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

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

핵심 개념

10진수를 k진수로 바꾸기

10진수를 k진수로 바꾸는 방법을 알아야 합니다.
방법은 다음과 같습니다.

1. 대상 숫자를 k로 나눈 나머지가 아직 정해지지 않은 가장 오른쪽 자릿수가 됩니다.
2. 대상 숫자가 0 이하가 될 때까지 반복합니다.

Python으로 작성한 코드는 다음과 같습니다.

def k_notation(decimal, k):
    result = ""

    while decimal > 0:
        decimal, mod = divmod(decimal, k)
        result += str(mod)

    return result[::-1]

소수인지 판별하기

소수 판별 문제에는 특별히 효율적인 알고리즘이 존재하지 않습니다.
대상 숫자를 2부터 제곱근까지 조사하여 나누어 떨어지는지 조사해야 합니다.
다만 1을 소수로 판별하지 않도록 주의해야 합니다.

Python으로 작성한 코드는 다음과 같습니다.

def is_prime(number):
    number = int(number)

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

    return True

str 자료형에서 원하는 패턴 찾기

k진수로 변환된 n에서 P를 찾는 방법을 알아야 합니다.
문제는 4가지로 나눠서 설명하고 있지만, 실제로는 전체 문자열에서 0이 포함되지 않은 부분을 나눠서 표현한 것입니다.

 

테스트케이스로 제공된 437674을 3진수로 바꾸는 경우를 살펴보겠습니다.
3진수로 변환하면 211020101011입니다.

 

1번째 경우(0P0): 2, 1, 1
2번째 경우(P0): 211
3번째 경우(0P): 11
4번째 경우(P): 없음

 

앞에서부터 0이 포함되지 않은 부분을 나열하면 211, 2, 1, 1, 11입니다.
직관적으로 두 가지 방법론이 사실 같은 것임을 알 수 있습니다.

 

전체 문자열에서 0이 포함되지 않은 연속된 숫자 문자열은 정규식을 이용해서 쉽게 찾을 수 있습니다.

Python 정규식에 대해서는 다음 링크를 참고해주세요.
https://docs.python.org/ko/3/howto/regex.html

정규식 HOWTO — Python 3.10.2 문서

Python으로 작성한 코드는 다음과 같습니다.

import math
import re

def solution(n, k):
    target = k_notation(n, k)
    match = re.findall("[1-9]*", target)

    answer = 0
    for case in match:
        if case != "":
            if is_prime(case):
                answer += 1

    return answer

풀이

전체 코드는 다음과 같습니다.

import math
import re

def solution(n, k):
    target = k_notation(n, k)
    match = re.findall("[1-9]*", target)

    answer = 0
    for case in match:
        if case != "":
            if is_prime(case):
                answer += 1

    return answer

def k_notation(decimal, k):
    result = ""

    while decimal > 0:
        decimal, mod = divmod(decimal, k)
        result += str(mod)

    return result[::-1]

def is_prime(number):
    number = int(number)

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

    return True