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

문제

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

 

1. 0P0 처럼 소수 P의 양쪽에 0이 있는 경우

2. P0 처럼 소수 P의 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우

3. 0P 처럼 소수 P의 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우

4. P 처럼 소수 P의 양쪽에 아무것도 없는 경우

5. 단, P는 각 자릿수에 0을 포함하지 않는 소수이다. ex) 101은 소수 P가 될 수 없다

 

예를 들어 437674를 3진수로 바꾸면 211020101011이다.

여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽에서부터 211, 2, 11이 있으며, 총 3개 이다(211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의).

211은 P0의 형태, 2는 0P0의 형태, 11은 0P의 형태에서 찾을 수 있다.

 

정수 n과 k가 매개변수로 주어진다.

n을 k진수로 변환했을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. n은 1 이상 1,000,000 이하의 자연수

2. k는 3 이상 10 이하의 자연수

 

 

코드

import re
from math import sqrt

def solution(n, k):
    def convert_notation(n, base):
        T = '0123456789ABCDEF'
        quotient, remainder = divmod(n, base)

        return convert_notation(quotient, base) + T[remainder] if quotient else T[remainder]

    def isPrime(num):
        for i in range(2, int(sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

    converted_n = convert_notation(n, k)
    r = re.compile('[1-9]*')

    answer = 0
    for num in r.findall(converted_n):
        if num != '' and num != '1':
            if isPrime(int(num)):
                answer += 1
    
    return answer

 

 

설명

처음에는 조건에 맞게 정규표현식 패턴을 4개 만들어 문제를 풀었는데

생각해보니 그럴 필요가 없다는 것을 도중에 알게 됐다.

 

소수 P는 각 자릿수에 0이 없기 때문에 그냥 0을 제외한 숫자들을 찾아서 소수판별을 하면 되는 간단한 문제다.

 

def convert_notation(n, base):
	T = '0123456789ABCDEF'
	quotient, remainder = divmod(n, base)

	return convert_notation(quotient, base) + T[remainder] if quotient else T[remainder]

base진수 변환 함수이다.

n을 base진수 변환하여 문자열로 결과를 반환한다.

 

def isPrime(num):
	for i in range(2, int(sqrt(num)) + 1):
		if num % i == 0:
			return False
	return True

소수 판별 함수이다.

 

converted_n = convert_notation(n, k)

 

n을 k진수로 변환한 값을 converted_n에 저장한다.

 

r = re.compile('[1-9]*')

정규표현식의 패턴이다.

1~9의 숫자들이 연속해서 등장하는 패턴을 의미한다.

 

answer = 0
for num in r.findall(converted_n):
	if num != '' and num != '1':
		if isPrime(int(num)):
			answer += 1

converted_n 문자열에 r패턴에 맞는 문자열들을 찾아 그 문자열들을 하나씩 꺼내며 반복한다.

만약 num이 빈 문자열이거나 '1'이면 이후 동작없이 그냥 넘어간다.

그렇지 않을 경우 num을 int로 형변환해준뒤 소수인지 판별한다.

소수라면 answer에 1을 더한다.

 

return answer

반복이 끝나면 answer를 반환한다.