BOJ 5376 - 소수를 분수로

문제

소수(decimal)를 기약 분수로 변환하라. 순환소수는 괄호로 순환 부분이 표시된다.

입력

테스트 케이스 수 N과 각 소수 문자열이 주어진다. 순환 부분은 괄호로 표시 (예: 0.1(6)).

출력

각 소수를 기약 분수로 출력한다.

예제

입력	출력
`3` `0.2` `0.(3)` `0.1(6)`	`1/5` `1/3` `1/6`

풀이

순환소수와 유한소수를 분리하여 분수로 변환한다.

유한소수: 소수 부분을 분자, 10^(자릿수)를 분모로 한다
순환소수: 비순환부와 순환부를 분리하여 (전체수 - 비순환수) / (999...0...0) 공식을 적용한다
GCD로 약분하여 기약 분수로 출력한다

핵심 아이디어: 순환소수 0.a(b)의 분수 표현에서 분모는 9가 순환부 길이만큼 + 0이 비순환부 길이만큼 붙은 수이다.

코드

from math import gcd
 
 
def to_fraction(s):
    s = s.strip()
    if "(" not in s:
        decimal = s[2:]
        numerator = int(decimal)
        denominator = 10 ** len(decimal)
    else:
        prefix, repeat = s.split("(")
        repeat = repeat.strip(")")
        non_repeat = prefix[2:]
 
        full = non_repeat + repeat
        full_val = int(full)
        base_val = int(non_repeat) if non_repeat else 0
 
        len_non = len(non_repeat)
        len_repeat = len(repeat)
 
        numerator = full_val - base_val
        denominator = (10**len_non) * (10**len_repeat - 1)
 
    g = gcd(numerator, denominator)
    return f"{numerator // g}/{denominator // g}"
 
 
n = int(input())
for _ in range(n):
    print(to_fraction(input()))

복잡도

시간: O(log N)
공간: O(1)

문제