[Python] k진수에서 소수의 개수 구하기 (2022 Kakao)

이 문제는 2022년도 카카오 신입 공채 1차 온라인 코딩 테스트에서 출제된 문제이며 프로그래머스에서 풀이했습니다.

문제 설명

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

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

예를 들어, 437674 을 3 진수로 바꾸면 211020101011 입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11 이 있으며, 총 3 개입니다. 211 은 P0 형태에서 찾을 수 있으며, 2 는 0P0 에서, 11 은 0P 에서 찾을 수 있습니다.

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

제한 사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입출력 예

n	k	결과
437674	3	3
110011	10	2

풀이

이 문제는 3단계로 나누어서 풀 수 있습니다.

1. 주어진 n을 k진수로 변환합니다.
2. 0을 기점으로 수를 분할합니다.
3. 분할된 수에 대해서 소수인지 판별합니다.

Step 1과 2는 문자열로 취급해서 간단하게 처리할 수 있습니다.
Step 3은 효율성을 고려해서 에라토스테네스의 체를 활용하는 방법이 있고 아니면 2~√𝑛 까지 나 누어지는 수가 있는지 확인하는 방법이 있습니다.

해설

n = 1000000
era = [False, False] + [True]*(n-1)

for i in range(2, n+1):
	if era[i]:
    	for j in range(i*2, n+1, i):
        	era[j] = False

에라토테네스의 체를 활용해서 Prime Number에 대한 리스트를 미리 생성합니다.

def ten_to_k(n, k):
	ret = ""
    while n > 0:
    	ret += str(n % k)
        n //= k
    return ret[::-1]

N을 k진수로 변환하는 함수를 작성합니다.
손으로 진법 변환하는 과정을 그대로 구현한 것입니다.

def solution(n, k):
    answer = ten_to_k(n, k)
    answer = answer.split("0")
    
    counter = 0
    for a in answer:
        if a == "" or a == "1":
            continue
            
        if era[int(a)]:
            counter += 1
        
    return counter

변환된 문자열에 대해 "0"을 기점으로 분할합니다.
이때, 0이 연속적으로 나온 경우 빈 문자열("")이 나오거나 101 같은 경우에는 소수가 아니기 때문에 "1"도 무시합니다.
마지막으로 에라토스테네스의 체로 미리 세팅한 테이블에서 소수인지 찾아봅니다.
소수인 경우 counter 변수에 1을 더하고 마지막에 counter를 return 합니다.

하지만, 여기서 문제가 발생합니다.
N을 k진수로 변환하게 되면 P가 n보다 클 수도 있고 시간이 매우 많이 소요될 수 있기 때문에 이 문제에서 에라토스테네스의 체를 사용하기 어렵습니다.
따라서 두 번째 풀이 방법인 2~√𝑛까지 계산하는 방법을 사용해야 합니다.

def isPrime(n):
    if n <= 1:
        return False
    else:
        for i in range(2, int(n**0.5)+1):
            if n%i == 0:
                return False
        return True

# if era[int(a)]:
if isPrime(int(a)):

√𝑛까지만 검증하는 함수를 작성하고 solution 함수에서 소수 판별하는 부분을 변경해줍니다. 

코드

def ten_to_k(n, k):
    ret = ""
    while n > 0:
        ret += str(n % k)
        n //= k
    return ret[::-1]

def isPrime(n):
    if n <= 1:
        return False
    else:
        for i in range(2, int(n**0.5)+1):
            if n%i == 0:
                return False
        return True
    
def solution(n, k):
    answer = ten_to_k(n, k)
    answer = answer.split("0")
    
    counter = 0
    for a in answer
        if a == "" or a == "1":
            continue
            
        if isPrime(int(a)):
            counter += 1
        
    return counter

실행 결과