5376번: 소수를 분수로

문제 출처 : https://www.acmicpc.net/problem/5376

 

언어 : Kotlin

 

문제 설명 :

유리수 분수를 소수로 나타내면, 소수점 아래 자리가 유한 개인 경우(1/8 = 0.125)와 어떤 자리에서부터 일정한 숫자가 한없이 되풀이 되는 경우(1/11 = 0.090909...)가 있다.

소수를 입력받은 뒤, 분수로 나타내는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다. 각 테스트 케이스는 한 줄에 소수가 하나씩 주어진다.

소수의 첫 두 자리는 "0."이다. 그 다음에는 숫자 0개~6개가 주어진다. 그 다음, 길이가 1과 9사이면서 괄호로 감싸져있는 수가 주어질 수도 있다. 이 수는 무한히 반복되는 자리를 의미한다.

항상 0이 아닌 자리가 하나는 주어지며, 괄호 안에 주어지는 수는 0이나 9로만 이루어져 있지 않다.

 

출력 :

각 테스트 케이스에 대해서, 입력으로 주어진 소수의 분수 표현을 출력한다. (분모와 분자는 서로소이어야 한다)

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
3 0.5 0.(3) 0.6(142857)	1/2 1/3 43/70

 

풀이 : 

문제에서 나와있듯 유한소수일때와 무한소수일때를 나눠 구현해야한다.

문자열을 유한소수일때와 무한소수일때를 나눈다음, 무한소수 부분이 비었다면 유한소수이다.

 

단순하게 소수를 분수형태로 바꿀때 소수점 자리수에 따라 분자 분모에 10 * 소수점 자리수를 해준 다음 유클리드 호제법을 사용해 최대공약수를 구한 후, 분자와 분모를 단순화하여 표현해준다.

 

무한소수일 경우, 유한 소수부분과 무한소수 부분을 구분해야한다.

예를 들어 0.6(142857)이 주어졌을 경우.

유한한 부분은 0.6

무한한 부분은 (142857)이 된다.

 

계산의 편리함을 위해 그 두 부분의 각각 길이를 구해서 유한한 부분은 6만 남기고, 무한한 부분은 142857만 남긴다.

위와 같이 남기기 위해 코드상으로 각 두 길이에 10을 제곱하여 소수점 자리를 없애주는 것이다.

 

그러면 6 * 10^6 + 142857이 분자부분이 되게 된다.

 

분모는 다음과 같다.

무한한 부분을 나타내기 위해 10^무한한 부분의 길이 - 1 = 10^6 - 1 = 999999

유한한 부분을 나타내기 위해 10^유한한 부분의 길이 = 10^1 = 10

 

분자 분모를 구했으니 둘을 유클리드 호제법을 통해 최대공약수를 구하고 이를 사용해 분수를 단순화 시킨다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.abs
import kotlin.math.pow

data class Fraction(val numerator: Long, val denominator: Long)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    repeat(readLine().toInt()) {
        val fraction = convertDecimalToFraction(readLine())
        bw.appendLine("${fraction.numerator}/${fraction.denominator}")
    }
    bw.flush()
    bw.close()
}

fun convertDecimalToFraction(decimal: String): Fraction {
    val nrp = decimal.substringBefore('(')
    val nrpl = nrp.substringAfter('.', "").length

    val rp = decimal.substringAfter('(', "").substringBefore(')')
    val rpl = rp.length

    return if (rp.isEmpty()) {
        val scale = 10.0.pow(nrpl).toLong()
        val numerator = (decimal.toDouble() * scale).toLong()

        simplifyFraction(numerator, scale)
    } else {
        val integerPart = nrp.substringBefore('.').toLong()
        val npDecimal = nrp.substringAfter('.', "")
        val npDecimalValue = if (npDecimal.isEmpty()) 0L else npDecimal.toLong()

        val numerator = integerPart * 10.0.pow(nrpl + rpl).toLong() +
                npDecimalValue * 10.0.pow(rpl).toLong() +
                rp.toLong() -
                integerPart * 10.0.pow(nrpl).toLong() -
                npDecimalValue

        val denominator = (10.0.pow(rpl) - 1).toLong() * 10.0.pow(nrpl).toLong()

        simplifyFraction(numerator, denominator)
    }
}

fun simplifyFraction(numerator: Long, denominator: Long): Fraction {
    val gcdValue = gcd(numerator, denominator)
    return Fraction(numerator / gcdValue, denominator / gcdValue)
}

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