k진수에서 소수 개수 구하기(카카오) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

주어진 정수 N 을 k 진수로 변환해서 해당 숫자에서 소수의 개수가 몇 개인지 구하는 문자열 관련 구현 문제이다. 

이때, 0을 기준으로 숫자를 분리해서 소수 판별을 진행해야한다. 

 

 

처리과정

1. 숫자 N을 K 진수로 변환한다
2. 0을 기준으로 숫자를 분리한다
3. 각 숫자들에 대해 소수 여부를 판별하고 개수를 센다

 

위의 과정에서 K 진수로의 변환, 소수 여부 판별에 대한 처리가 필요하며 이를 위해 함수를 만들어서 처리를 했다.

 

 

K 진수 변환

숫자를 k로 계속 나눠가면서 나머지모아 문자열로 만든다

https://www.rohm.co.kr/electronics-basics/da-converters/da_what3

 

def convert(num,k):
    ret=""
    while num>0:
        ret=str(num%k)+ret
        num=num//k
    return ret

 

 

소수 여부 판별

소수라면 1과 자기 자신 이외의 숫자로 나눠떨어지면 안된다. 이러한 특징을 활용해서 2부터 숫자를 나눠가며 나눠떨어지는지를 확인한다.  이때, n-1까지 나눠보는 것이 아닌 제곱근 까지의 수만 나누면 된다(대칭성). 

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

 

 

시간 복잡도

숫자 N을 k 진수로 변환시에 O(logN) 의 시간이 걸리고, 변환한 수를 0을 기준으로 분리한 숫자 M개에 대해서는 O(√M)의 시간이 걸린다. 전체적인 시간복잡도는 O(logN + √M) 이며, N의 최댓값은 10^6, M의 최댓값은 대략 2^21 ≒ 2*10^6 이기 때문에 시간내에 동작한다

 

 

코드

from math import sqrt
def convert(num,k):
    ret=""
    while num>0:
        ret=str(num%k)+ret
        num=num//k
    return ret

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

def solution(n, k):
	# k 진수로 변환 후, "0"을 기준으로 분리한다
    nums=convert(n,k).split("0")
    nums=[num for num in nums if num!="" ]
    
    answer=0
    prime_nums=set() # 기존에 판별했던 소수를 저장해서 소수 중복 판별 X
    
    for num in nums:
        num=int(num)
        
        # 이미 검사한 소수라면 개수를 증가시키고 continue
        if num in prime_nums:
            answer+=1
            continue
            
        elif is_prime(num): # 그렇지 않다면 검사를 진행한다
            prime_nums.add(num)
            answer+=1
            
    return answer