[LeetCode] 166. Fraction to Recurring Decimal

Problem

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.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Constraints:

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

---

Solution

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0)
            return "0";
        
        StringBuilder result = new StringBuilder();
        
        result.append(0 < numerator ^ 0 < denominator ? "-" : "");
        
        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);
        
        result.append(num / den);
        
        long remainder = num % den;
        if (remainder == 0)
            return result.toString();
        result.append(".");
        
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        // 소수 부분 중 반복 존재 여부 확인
        while (!map.containsKey(remainder)) {
            map.put(remainder, result.length());
            result.append(remainder * 10 / den);
            remainder = remainder * 10 % den;
        }
        int index = map.get(remainder);
        result.insert(index, "(");
        result.append(")");
        return result.toString().replace("(0)", "");
    }
}

Explanation

• String 타입을 만들어서 반환하기 위한 방법 중 하나인 String Builder 타입의 변수 result를 선언한다.

  StringBuilder result = new StringBuilder();
  

• 나눗셈을 수행할 때, 계산 결과의 부호를 먼저 계산해 놓지 않으면, 나머지를 구할 때 계속해서 부호가 따라다니는 경우가 생길 수 있으므로, 부호를 미리 계산해 result 변수에 추가해준다.

  result.append(0 < numerator ^ 0 < denominator ? "-" : "");
  

• 소수점 이하 부분이 반복되면 괄호를 만들어 주어야 하기 때문에, 정수 부분과 소수 부분을 나누어서 생각해 본다.
• 부호를 앞서 구해놓았기 때문에, 분자와 분모의 절대값으로 계산을 진행해야 하므로 분자와 분모를 절대값으로 변경하여 정수부분을 구한 뒤 변수 result에 합쳐준다.
• 32비트 정수가 가질 수 있는 범위는 -2^31 ~ 2^31-1이 되는데, -2^31 값을 절대값으로 변경하면, 범위를 벗어나는 Overflow가 발생하여 원하는 결과를 얻지 못한다. 따라서 분자와 분모를 모두 Long 타입으로 변환하여 절대값으로 바꿔준 뒤, Long 타입 변수 num과 den에 할당해준다.

        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);
        result.append(num / den);
  

• 소수 부분을 나타내기 위해 변수 remainder을 선언하고, 소수 부분 없이 나눗셈이 수행되면 변수 result의 값을 String 타입으로 변환한 뒤 반환하도록 if 조건문을 작성한다.
• 소수 부분을 계산하기 전에 변수 result에 소수 점을 추가해준다.

  long remainder = num % den;
  if (remainder == 0)
    return result.toString();
  result.append(".");
  

• 소수 부분에서 반복되는 부분이 존재하면 괄호를 만들어 주어야 하는데, 소수 반복된다는 특징을 생각했을 때, 자료구조 Set이나, Map의 Key를 생각할 수 있다.
• 소수 부분에서는 반복되는 부분의 index가 필요하므로, Map의 Key에는 소수 부분을 한자리 씩 추가해주고 Value에는 자리 수를 나타내기 위해서 변수 result의 길이를 할당한다.
• while 반복문에 조건식을 작성해 반복 되는 부분이 등장하면 반복을 종료하도록 한다.

  Map<Long, Integer> map = new HashMap<Long, Integer>();
  // 소수 부분 중 반복 존재 여부 확인
  while (!map.containsKey(remainder)) {
    map.put(remainder, result.length());
    result.append(remainder * 10 / den);
    remainder = remainder * 10 % den;
  }
  

• while 반복문을 빠져나오면, 반복되는 부분에 괄호를 추가하는 작업을 한다. ```java int index = map.get(remainder); result.insert(index, “(“); result.append(“)”);

- 변수 result의 마지막 부분에 (0)이 추가되는 경우가 있으므로 이를 제거하고 변수 result를 String 타입으로 변환하여 반환한다.
```java
return result.toString().replace("(0)", "");