프로그래머스[programmers] - k진수에서 소수 개수 구하기(Kotlin)[LV3]

문제

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

프로그래머스

 

문제 풀이

N에 대한 k진수를 구하고 소수 판별에 대한 최적화만 할 수 있다면 쉽게 풀 수 있는 문제이다.

1번 테케에서 틀렸던 사람들은 자료형을 바꾼다면 아마 통과할것이다.

 

기본적인 k진수 구하기 알고리즘은 k로 나눈 나머지를 저장해서 거꾸로 바꾼다면 아마 그것이 N에 대한 k진수일것이다.

문제에서 요구사항은 N으로 끊어서 그 수가 소수인지 아닌지만 판단하면 된다.

추가적으로 N에 0이 포함되어 있다면 소수가 아니다.

 

소수를 구하는 알고리즘은 간단하다.

에라토스테네스의 체를 이용하면 되는데,

2~n-1까지의 모든 숫자를 n과 나눠서 나누어떨어지는지 검사하는 방법은 매우 바보같은 방법이다.

예를 들어 12가 있다고 가정하자.

12의 약수는 1,2,3,4,6,12이다.

12가 소수인지 판단을 하기 위해서 2~12까지 모든 숫자를 대입해서 검사를 해야한다? 그것은 효율적이지 못하다.

왜냐하면 약수가 있다면 그 약수에 해당하는 또다른 숫자가 있기 마련이다.

2가 있으면 6이 있듯이 반듯이 반대편의 숫자와 매칭이 된다. 따라서 우리는 범위를 조절할 수 있다.

이러한 범위를 조절하는 알고리즘이 에라토스테네스의 체이다.

우리는 12를 반으로 쪼개서 12의 반에 해당하는 범위까지 검사하면 된다. 해당 범위에서 약수가 존재하지 않는다면 그 수는 약수가 없을 것이다.

따라서 소수 판별의 알고리즘은 N을 N-1까지 검사하는것이 아닌 N을 √N 까지 검사하면 된다.

 

 

코드

import kotlin.math.*
class Solution {
    fun solution(n: Int, k: Int): Int {
        return converteDivideK(n,k)
    }
    
    fun converteDivideK(n : Int, k : Int) : Int{
        var num = n
        var sum = 0
        var result = ""
        while(num>0){
            val divide = num%k
            result += divide.toString()
            num/=k
        }
        val numbers = result.reversed().split("0")
        for(number in numbers){
            if(isPrime(number)){
                sum++
            }
        }
        return sum
    }
    fun isPrime(n:String) : Boolean{
        if(n.toLongOrNull()==null || n.toLong()==1L)
            return false
        val num = n.toLong()
        for(i in 2 .. sqrt(num.toDouble()).toInt()){
            if(num%i==0L){
                return false
            }
        }
        return true
    }
}