프로그래머스 > k진수에서 소수 개수 구하기 (Python 3)

 

1. 문제 설명

양의 정수 n을 k 진수로 바꿨을 때, 변환된 수 안에 소수 (prime number)가 몇 개인지 알아보려고 한다.

 

- 0P0 : 소수 양쪽에 0이 있는 경우

- P0 : 소수 오른쪽에만 0이 있고, 왼쪽에는 아무것도 없는 경우

- 0P : 소수 왼쪽에만 0이 있고, 오른쪽에는 아무것도 없는 경우

- P : 소수 양쪽에 아무것도 없는 경우

 

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

소수는 211, 2, 11이므로 총 3개이다. 이때, 중복되는 원소에 대해서는 중복으로 세어준다.

 

 

 

2. 코드

(1) 1차 시도

def conversion(n, k):
    res = []
    
    while n > 0:
        res.append(str(n % k))
        
        n = n // k
    return ''.join(list(reversed(res)))

def is_prime(n):
    if n == 1:
        return False
    
    for i in range(2, n):
        if n % i == 0:
            return False
    
    return True
        
def solution(n, k):
    res = conversion(n, k)
    candidates = res.split('0')
    primes = 0
    
    for candidate in set(candidates):
        try:
            if is_prime(int(candidate)) == True:
                primes += candidates.count(candidate)
        except ValueError:
            continue
    
    return primes

 

 

(2) 2차 시도

def conversion(n, k):
    if k == 10:
        return str(n)
    
    res = ''
    
    while n > 0:
        n, mod = divmod(n, k)
        res += str(mod)
    
    return res[::-1]

def is_prime(n):
    if n == 1:
        return False
    
    for i in range(2, int(n ** (1/2)+1)):
        if n % i == 0:
            return False
    
    return True
        
def solution(n, k):
    res = conversion(n, k).split('0')

    primes = 0
    
    for candidate in set(res):
        try:
            prime_or_not = is_prime(int(candidate))
            
            if prime_or_not == True:
                   primes += res.count(candidate)
                   
        except ValueError:
            continue
        
    return primes

 

 

 

 

3. 설명

첫번째 시도 때에는 시간 초과가 발생해서, 최대한 줄일 수 있는 부분을 찾아서 고쳤다.

 

(1) conversion 함수

- 진수 변환에서 10진수인 경우에는 그대로 반환하기

- 진수 변환에서 직접 mod 연산과 몫 연산을 하기 보다는 divmod 함수 사용하기

- 리스트를 revered, join 하지 말고 string 타입으로 반환 시에는 [::-1]을 사용하여 역순으로 만들기

 

 

(2) is_prime 함수

- n까지 모두 다 검토하지 말고, n의 제곱근까지만 검토하기

 

 

(3) 동일한 코드

- 진수 변환한 문자열에 대해서 0을 기준으로 split 하기

- split한 문자열을 미리 정수로 바꾸지 말고, try ~ except를 사용해서 int로 바꿀 수 없는 문자열 (예. '')인 경우는 continue 해주기

- 동일한 문자가 존재할 수 있기 때문에 set을 사용해서 한번씩만 검토하되, count로 동일한 원소 개수를 정답에 더해주기