[Kotlin] 백준 11082 : 소수를 분수로

문제 링크

11082번: 소수를 분수로

---

문제 해설

소수의 형태로 주어지는 유리수를 기약분수로 치환해야 한다.

 

우선 입력으로 주어지는 수는 정수, 유한소수, 순환소수 3가지의 경우로 구분할 수 있다. 각 경우에 대해서 생각해보자.

 

• 정수인 경우

예제 1과 같이 단순히 분자가 입력으로 주어진 수이고 분모가 1인 형태로 나타내면 된다.

println("$decimal/1")

• 유한소수인 경우

소수부의 길이가 \(n\)이라고 할 때, 유한소수를 분수로 나타내는 가장 쉬운 방법은 입력에서 소수점을 제거한 수가 분자가 되고 \(10^n\)이 분모인 분수로 표현하는 것이다. 이후 분자와 분모의 최대 공약수를 구하여 분자와 분모를 각각 최대 공약수로 나누어 기약분수로 나타내면 된다.

val decimalLong = decimal.replace("[.()]".toRegex(), "").toLong()
val denominator = "1${"0".repeat(decimalPart.length)}".toLong()
val gcd = gcd(decimalLong, denominator)
println("${decimalLong / gcd}/${denominator / gcd}")

• 순환소수인 경우

소수부를 소괄호로 감싸져있는 순환부와 그 외의 비순환부로 나눈다. 이 때, 분모는 9가 순환부의 길이만큼 나타나고 0이 비순환부의 길이만큼 나타나는 수가 된다. 예를 들어, 0.1(31)의 경우에는 분모가 990이 된다.

 

분자는 (입력에서 소수점을 제거한 수) - (입력에서 소수점을 제거한 후 순환부를 제외한 수)가 된다. 앞서 예시로 들었던 0.1(31)의 경우를 보자.

 

1. 0.1(31)에서 소수점을 제거하면 131이 된다.
2. 위의 131에서 순환부를 제외한 수는 1이 된다.
3. 최종적으로 분자는 \(131-1=130\)이 된다.

 

분자와 분모를 모두 구했으니 최종적으로 분자와 분모를 각각 최대 공약수로 나누어 기약분수로 나타내면 된다.

val decimalLong = decimal.replace("[.()]".toRegex(), "").toLong()
val loopStartIndex = decimalPart.indexOf('(')
val loop = decimalPart.substring(loopStartIndex + 1, decimalPart.length - 1)
val nonLoop = decimalPart.substring(0, loopStartIndex)
val denominator = ("9".repeat(loop.length) + "0".repeat(nonLoop.length)).toLong()
val numerator = decimalLong - "$integerPart$nonLoop".toLong()
val gcd = gcd(numerator, denominator)
println("${numerator / gcd}/${denominator / gcd}")

 

분자와 분모의 최대 공약수는 유클리드 호제법을 사용해서 구한다.

private fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)

Code

fun main() = with(System.`in`.bufferedReader()) {
    val decimal = readLine()
    val integerPart = decimal.substringBefore('.').toLong()
    val decimalPart = decimal.substringAfter('.', "-1")
    if (decimalPart == "-1") {
        println("$decimal/1")
        return@with
    }
    val decimalLong = decimal.replace("[.()]".toRegex(), "").toLong()
    val loopStartIndex = decimalPart.indexOf('(')
    if (loopStartIndex == -1) {
        val denominator = "1${"0".repeat(decimalPart.length)}".toLong()
        val gcd = gcd(decimalLong, denominator)
        println("${decimalLong / gcd}/${denominator / gcd}")
        return@with
    }
    val loop = decimalPart.substring(loopStartIndex + 1, decimalPart.length - 1)
    val nonLoop = decimalPart.substring(0, loopStartIndex)
    val denominator = ("9".repeat(loop.length) + "0".repeat(nonLoop.length)).toLong()
    val numerator = decimalLong - "$integerPart$nonLoop".toLong()
    val gcd = gcd(numerator, denominator)
    println("${numerator / gcd}/${denominator / gcd}")
}

private fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)