[카카오 기출/kotlin] k진수에서 소수 개수 구하기

문제 : k진수에서 소수 구하기

배운 점 및 필요한 개념 정리

• 10진수 n을 k진수로 변환 : n.toString(k)

  • 원래는 이거 직접 구현했었음! 마무리 reversed 잊지말기

      private fun convert10ToK(n: Int, k: Int): String {
          var temp = n
          var str = ""
    
          while (temp >= 0) {
              str += temp % k
              temp /= k
              if (temp == 0) break
          }
          return str.reversed()
      }

• n이 소수(prime)인지 판별 :n을 2이상 sqrt(n) ‘이하’의 수로 나눠본다

  • 이에 대한 인사이트를 주는 글

    

• 자매품으로 에라토스테네스의 체가 있다. 아래 로직을 보면 너무 당연하다

  • [예제] 26이하의 자연수 중 소수가 뭐뭐 있는지 판별하기
    • 2배수 지워
    • 3배수 지워
    • 4는 이미 2배수에서 제외됨
    • 5배수 지워
    • 제곱근이 5.xxx 이니까 여기까지만 검사하면 된다!
  • 참고한 블로그👍 : https://velog.io/@changhee09/알고리즘-소수의-판별-에라토스테네스의-체

• kotlin에서 제공하는 sqrt(n) 함수의 경우, n이 double형이다.

  • 따라서 n 값으로 정수값을 활용하고자 하는 경우 sqrt(n.toDouble) 함수와 함께 더불어 사용해야한다
  • sqrt(n)의 결과값 또한 double형이 도출되기에, 이 또한 toInt() 혹은 toLong() 함수와 함께 사용할 수 있다.

• import 잊지말아라! import kotlin.math.sqrt

오래걸린 이유

1. Long 타입 고려 안함
   1. 입출력 범위는 Int임이 확실했음
   2. 그러나 k진수로 변환할 경우, 그 자리수가 길어지면서 int 범위를 넘어갈것이라는 고려를 못함
2. 소수 판별 로직 엣지케이스 고려 안함
   1. 제곱근 n ‘이하’의 수까지 고려해야하는데, ‘미만’까지 검사함
   2. 따라서 n이 소수인지 아닌지 제대로 도출할 수 없었음
   3. 예를들어 49가 소수인지 판별하려면 2.. 7을 포함한 값까지 검사해야함

최종 코드

import kotlin.math.sqrt


class Solution {

    private fun Long.isPrime(): Boolean {
        val n = this@isPrime
        if (n <= 1) return false // 2보다 큰 자연수 중에
        for (i in 2 until sqrt(n.toDouble()).toLong()) {
            if (n % i == 0L) return false
        }
        return true    // 모두 반복해도 나누어 떨어지지 않으면 소수
    }

    fun solution(n: Int, k: Int): Int {
        val convertedNum = n.toString(k)
        var answer = 0

        convertedNum.split("0")
            .filter { it.isNotEmpty() } // 00의경우 split을 적용하면 ""이 나옴
            .map { it.toLong() }
            .groupingBy { it }
            .eachCount()
            .filter { it.key.isPrime() }
            .onEach { answer += it.value }

        return answer
    }
}