2024.06.27 TIL 코트카타 95번(k진수에서 소수 개수 구하기)

    fun solution(n: Int, k: Int): Int {
        var answer = 0
        val convertedK = convertTenToK(n, k).toString()
        var dividedN = StringBuilder()

        for (convertedChar in convertedK) {
            if(convertedChar != '0')
                dividedN.append(convertedChar)
            else if(dividedN.isEmpty())
                continue
            else if(isPrime(dividedN.toString())) {
                answer++
                dividedN.clear()
            } else
                dividedN.clear()
        }

        if(dividedN.isNotEmpty() && isPrime(dividedN.toString()))
            answer++

        return answer
    }

    fun convertTenToK(number: Int, k: Int): Long{
        val convertedNumber = StringBuilder()
        var share = number / k
        var remain = number % k

        while (share >= k) {
            convertedNumber.insert(0, remain)
            remain = share % k
            share /= k
        }

        convertedNumber.insert(0, remain)
        convertedNumber.insert(0, share)

        return convertedNumber.toString().toLong()
    }

    fun isPrime(number: String): Boolean{
        if(number == "1")
            return false

        val sqrtNumber = Math.sqrt(number.toLong().toDouble())

        for(divider in 2.. sqrtNumber.toLong()) {
            if((number.toLong() % divider).toInt() == 0)
                return false
        }

        return true
    }

 

풀이과정

1. n을 k진수로 변환한다.

2. 변환된 값을 반복문을 돌면서 0이 나오기 전까지 StringBuilder에 append한다.

3. 0이 나오면 이전까지 쌓인 값이 소수인지 확인한다.

   3.1. 소수면 답+1

   3.2. StringBuilder를 clear하고 2~3과정을 끝까지 반복한다.

 

포인트

- k진수 변환, 소수 검증을 함수로 분리해주고 구현하기