코틀린 코딩테스트 강좌, 신기한 소수 찾기

안녕하세요, 코딩테스트 강좌에 오신 것을 환영합니다. 오늘은 흥미롭고 도전적인 알고리즘 문제 ‘신기한 소수 찾기’를 해결해 보겠습니다. 이 문제는 주어진 범위 내에서 신기한 소수를 찾아내는 것입니다. 신기한 소수는 특정한 성질을 가지는 소수를 의미하며, 이를 통해 코딩테스트에 필요한 알고리즘적 사고를 기를 수 있습니다.

문제 설명

주어진 정수 N이 있을 때, 1부터 N까지의 모든 소수 중에서 그 소수가 신기한 소수인지 판단하는 프로그램을 작성하시오. 신기한 소수는 다음과 같은 조건을 만족해야 합니다:

소수 p의 모든 자릿수의 합이 또 다른 소수 q이어야 한다.
p의 모든 자릿수를 더하고, 이 합이 소수인 경우에만 신기한 소수로 인정한다.

예를 들어, 13의 경우 자릿수의 합은 1 + 3 = 4 이며, 4는 소수가 아니므로 13은 신기한 소수가 아닙니다. 하지만, 29의 경우 자릿수의 합은 2 + 9 = 11이고, 11은 소수이므로 29는 신기한 소수로 인정됩니다.

입력 및 출력 형식

입력:

첫 번째 줄에 정수 N (1 ≤ N ≤ 1000)이 주어진다.

출력:

N 이하의 신기한 소수를 오름차순으로 출력하시오.

문제 해결 전략

이 문제를 해결하기 위해서는 몇 가지 단계가 필요합니다:

1부터 N까지의 소수를 생성합니다.
각 소수에 대해 자릿수의 합을 계산합니다.
계산한 자릿수의 합이 소수인지 확인합니다.
신기한 소수를 모아 출력합니다.

알고리즘 구현

이제 알고리즘을 코드로 구현해 보겠습니다. 코틀린을 사용하여 이 문제를 해결하겠습니다. 아래의 코드에서 구현한 방식은 함수형 프로그래밍 스타일을 유지하며, 깔끔하게 작성하는 것을 목표로 하였습니다.


fun main() {
    val n = readLine()!!.toInt()
    val primes = generatePrimes(n)
    val curiousPrimes = mutableListOf()

    for (prime in primes) {
        if (isCuriousPrime(prime)) {
            curiousPrimes.add(prime)
        }
    }

    println(curiousPrimes.joinToString(" "))
}

fun generatePrimes(n: Int): List {
    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..n step i) {
                isPrime[j] = false
            }
        }
    }

    return (2..n).filter { isPrime[it] }
}

fun sumOfDigits(prime: Int): Int {
    return prime.toString().map { it.toString().toInt() }.sum()
}

fun isCuriousPrime(prime: Int): Boolean {
    val sum = sumOfDigits(prime)
    return isPrime(sum)
}

fun isPrime(num: Int): Boolean {
    if (num < 2) return false
    for (i in 2..Math.sqrt(num.toDouble()).toInt()) {
        if (num % i == 0) return false
    }
    return true
}

코드 설명

위의 코드를 단계별로 설명하겠습니다.

main 함수

프로그램의 진입점인 메인 함수에서는 사용자의 입력을 받고, 신기한 소수를 찾기 위한 함수를 호출합니다. 입력된 N값에 대해 소수를 생성하고, 각 소수에 대해 신기한 소수의 조건을 체크하여 결과를 리스트에 저장합니다.

generatePrimes 함수

이 함수는 주어진 N값까지 소수를 생성합니다. 에라토스테네스의 체 알고리즘을 사용하여 소수를 효율적으로 구하고, Boolean 배열을 통해 소수 여부를 체크합니다. 최종적으로 발견된 소수 리스트를 반환합니다.

sumOfDigits 함수

이 함수는 입력된 소수의 각 자릿수를 더한 후 그 합을 반환합니다. 문자열 변환과 매핑을 통해 각 자릿수를 정수로 바꾸고 합계를 계산합니다.

isCuriousPrime 함수

이 함수는 주어진 소수에 대해 자릿수의 합을 계산하고, 이 합이 소수인지 확인합니다. 이를 통해 신기한 소수를 판별합니다.

isPrime 함수

주어진 숫자가 소수인지 판별하는 함수입니다. 소수의 정의에 따라 2 이상인 경우에만 확인을 하고, 2부터 숫자의 제곱근까지 나눗셈을 통한 판별을 진행합니다.

실행 예시

주어진 예시로, N이 30일 경우 실행 결과는 다음과 같습니다:


2 3 5 11 23

마무리

오늘은 ‘신기한 소수 찾기’ 문제를 해결하며, 소수 및 자릿수의 합에 대한 이해를 높였습니다. 이 과정을 통해 코틀린을 활용한 알고리즘적 사고를 배울 수 있었고, 실제 코딩테스트에서도 적용할 수 있는 유용한 기법을 익혔습니다. 다음 시간에는 또 다른 흥미로운 알고리즘 문제를 다루어 보도록 하겠습니다. 감사합니다!

추가 학습 자료: