[Algorithm] 백준 - 소수 찾기 (2231) (Kotlin)

 

숫자가 주어지면 그 숫자의 가장 작은 생성자를 구하는 문제다. 주어진 숫자와 그 숫자의 일, 십, 백의 자리수 숫자를 더해서 분해합은 만들었지만 이후 로직을 짜지 못해서 풀지 못했다.

아래는 풀이 코드다.

 

fun main() {
    val n = readln().toInt()
    println(findSmallestConstructor(n))
}

fun findSmallestConstructor(n: Int): Int {
    for (i in 1 until n) {
        if (decompositionSum(i) == n) {
            return i
        }
    }
    return 0
}

fun decompositionSum(num: Int): Int =
    num + num.toString().sumOf { it.toString().toInt() }

 

문제에선 이 문제를 브루트 포스 알고리즘으로 풀 수 있다고 힌트를 준다.

브루트 포스는 간단히 말해서 모든 결과를 하나하나 다 따져보는 알고리즘으로, 위 코드는 반복문을 통해 1부터 입력받은 숫자까지의 모든 수를 순회하면서 그 수의 분해합이 N이 되는지 확인한다. 이 때 생성자가 있으면 가장 작은 값을 출력하고 없으면 0을 출력한다.

 

decompositionSum()의 sumOf는 각 자리수의 합을 더하기 위해 사용했다. 만약 278이란 숫자를 받으면 String으로 바꾸면 2, 7, 8로 나눌 수 있는데 이것을 Int로 바꿔서 모두 더하고 278에 더해서 분해합을 구한다.

다른 풀이는 아래와 같다.

 

fun main() {
    val num = readln().toInt()
    var result = 0

    for (i in (num - 9 * num.toString().length).coerceAtLeast(1) ..< num) {
        val sum = i + i.toString().sumOf { it.toString().toInt() }
        if (sum == num) {
            result = i
            break
        }
    }

    println(result)
}

 

일, 십, 백의 자리수에서 얻을 수 있는 숫자의 최대값은 9다. 그래서 num - 9 * num.toString().length를 통해 얻을 수 있는 최대합은 27이 된다. 왜냐면 num.toString()을 거치면 278의 경우 "278"이란 문자열이 되고, 이 문자열의 길이는 3이기 때문이다. 27을 받았다면 9 * 2 = 18이 각 자리수의 최대합이 된다. 이 처리를 통해 1부터 무작정 찾지 않고 일정 범위로 좁혀서 찾기 때문에 이전 방식보다 좀 더 효율적으로 작동한다.

또한 1부터 시작해야 하는데 이건 coerceAtLeast(1)를 써서 해결할 수 있다. 이 메서드가 무엇인지는 아래 공식문서를 확인한다.

 

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.ranges/coerce-at-least.html

coerceAtLeast - Kotlin Programming Language

이 값이 지정된 최소값보다 작지 않은지 확인한다. 최소값보다 크거나 같으면 이 값을 리턴하고 그게 아니면 최소값을 리턴한다

import java.time.DayOfWeek

fun main() {
    println(DayOfWeek.WEDNESDAY.coerceAtLeast(DayOfWeek.MONDAY)) // WEDNESDAY
    println(DayOfWeek.WEDNESDAY.coerceAtLeast(DayOfWeek.FRIDAY)) // FRIDAY
}

 

즉 앞에 위치한 숫자보다 coerceAtLeast()의 매개변수가 작다면 그 값을 최소값으로 사용하고, 앞의 위치한 숫자가 매개변수보다 작다면 그 숫자를 매개변수로 사용한다.