[LeetCode 풀이/python] 166. Fraction to Recurring Decimal (medium)

문제 설명: 분수에서 각각 분자와 분모를 나타내는 두 개의 정수가 주어졌을 때, 해당 분수의 값을 문자열(string) 형태로 리턴하시오. 분수 값에 반복되는 부분이 있을 경우, 해당 부분을 괄호로 감싸시오. 복수의 답이 가능할 경우 그 중 어느 답을 리턴해도 상관 없으며, 주어지는 모든 입력에 대해 정답 문자열의 길이는 10^4 을 넘지 않음이 보장된다.

 

(Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses. If multiple answers are possible, return any of them. It is guaranteed that the length of the answer string is less than 10^4 for all the given inputs.)

 

 

예시 1)

입력: numerator = 1, denominator = 2  -->  출력: "0.5"

 

예시 2)

입력: numerator = 2, denominator = 1  -->  출력: "2"

 

예시 3)

입력: numerator = 2, denominator = 3  -->  출력: "0.(6)"

 

예시 4)

입력: numerator = 4, denominator = 333  -->  출력: "0.(012)"

 

예시 5)

입력: numerator = 1, denominator = 5  -->  출력: "0.2"

 

제한 조건:

• -2^31 <= numerator, denominator <= 2^31 - 1
• denominator != 0

 

 

------ * ------ * ------ * ------

 

[풀이 1안] 

• 접근법
  • 기본적으로 divmod 함수를 이용해 몫에 해당하는 div 를 기록하고, 나누어 떨어지지 않는 경우 1) (유리수) 나머지가 0 이 될 때까지 연산을 반복하거나, 2) (무리수) 반복되는 패턴을 찾아냄
  • 나머지가 0 이 될 때까지 연산을 반복하는 것은, 나누어 떨어지지 않은 나머지의 자릿수를 한 자리씩 늘려 (mod* 10) 이를 새로운 분자로 삼는 것
    • 이전에 이미 분자(numerator) 로서 계산이 되었던 값이 다시 분자가 될 경우, 해당 부분이 반복되는 패턴의 시작점이 된다고 할 수 있음
    • 연산을 진행했던 분자들을 딕셔너리 storage 에 자릿수와 함께 저장하여 중복 여부 및 반복 패턴 확인 가능
    • 각각에 해당하는 몫은 별도 배열 deci 에 기록하여 소수점 이하 자릿수의 결과로 재구성
  • 분모가 0 인 경우는 존재하지 않으나 분자가 0 인 경우는 항상 0 이 되고, 분자/분모가 음수인 경우는 n_neg / d_neg flag 를 이용해 별도로 처리

 

• 코드 구현

def fractionToDecimal(numerator: int, denominator: int) -> str:
    res = ''
    n_neg, d_neg = 1, 1
        
    if numerator == 0: return '0' 
    elif numerator < 0:
        n_neg = -1
        numerator *= (-1)
    if denominator < 0:
        d_neg = -1
        denominator *= (-1)
            
    # num, denom 모두 positive 임을 보장        
    div, mod = divmod(numerator, denominator)
    res = res + str(div)
        
    deci = []
    storage = dict()
    if mod > 0:
        res = res + '.'
        while (mod > 0):
            numerator = mod * 10
            div, mod = divmod(numerator, denominator)
            if numerator in storage: break
            else: storage[numerator] = len(deci)
            deci.append(str(div))
                
    if mod == 0: 
        res = res + ''.join(deci)
    else: 
        k = storage[numerator]
        res = res + ''.join(deci[:k]) + '(' + ''.join(deci[k:]) + ')' 
            
    if (n_neg * d_neg > 0): return res
    else: return '-' + res
    

 

• 결과
  • 시간 복잡도를 O(n) 식으로는 어떻게 되는지 모르겠으나(...), 실제 값을 구하는 데에 있어 필요한 최소한의 나눗셈 연산을 수행하는 알고리즘 '-')!!