[LeetCode] 166. Fraction to Recurring Decimal

😎풀이

해당 문제는 순환 소수를 괄호로 묶어 풀어야 하는 문제이다.

소수점을 구하는 원리를 이해하고 풀면 훨씬 좋게 풀이할 수 있다.

예시: 4 ÷ 333)
초기 나머지: 4 % 333 = 4 → 정수 부분은 0, 나머지는 4.
소수 첫째 자리:
나머지 4 × 10 = 40
40 ÷ 333 = 0 → 몫 0 (소수 첫째 자리)
새로운 나머지: 40 % 333 = 40
소수 둘째 자리:
나머지 40 × 10 = 400
400 ÷ 333 = 1 → 몫 1 (소수 둘째 자리)
새로운 나머지: 400 % 333 = 67
소수 셋째 자리:
나머지 67 × 10 = 670
670 ÷ 333 = 2 → 몫 2 (소수 셋째 자리)
새로운 나머지: 670 % 333 = 4 (처음 나머지와 동일 → 반복 시작)
결과: 0.(012)

위 사항을 바탕으로 풀이 절차는 다음과 같다.

1. 소수점 계산을 위해 분모와 분자를 지속적으로 사용해야 하므로 음수 여부를 판별하여 절댓값으로 분모 분자를 저장함
2. 현재 몫과 나머지를 계산하여 나머지가 없다면 정수 부분만 반환
3. 나머지가 없을 때까지 반복하여 각 소수점 자리수를 계산함. 이 때 중요점은 나머지 값이 같은 상황이 발생할 경우 순환소수이므로 괄호 처리를 통해 반복문을 빠져나옴
   3-1. 순환소수인 경우 순환되는 부분에 괄호를 묶어 현재까지 나온 소수점과 함께 반환
   3-2. 순환소수가 아닌 상황에서 나머지가 0으로 나누어 떨어진 경우 현재까지 저장된 소수점 반환
4. 소수점을 문자화해 정답으로 반환

function fractionToDecimal(numerator: number, denominator: number): string {
    // 분자가 0이면 항상 0
    if(numerator === 0) return '0'
    // 음수처리 (분모, 분자 둘 중 하나만 음수라면 음수)
    const isNegative = (numerator < 0) !== (denominator < 0)
    let result = ''
    if(isNegative) result += '-'
    // 몫과 나머지 계산
    const num = Math.abs(numerator)
    const den = Math.abs(denominator)
    const quotient = Math.floor(num / den)
    result += String(quotient)
    let remainder = num % den
    // 나누어 떨어지는 경우 처리
    if(remainder === 0) return result
    // 나누어 떨어지지 않을 경우 소수점 추가
    result += '.'
    // key: 현재 나머지, value: 현재 위치
    const map = new Map<number, number>()
    // 소수점 배열
    const decimalPoint = []
    while(remainder !== 0) {
        // 나머지가 같은 값이 등장했다면 순환소수
        if(map.has(remainder)) {
            const pos = map.get(remainder)
            decimalPoint.splice(pos, 0, '(')
            decimalPoint.push(')')
            break
        }
        map.set(remainder, decimalPoint.length)
        // 현재 소수점을 구하기 위해 나머지에 10을 곱한 후 분모로 나누어 그 몫은 현재 소수점, 나머지는 다음 소수점을 구하기 위해 저장함
        remainder *= 10
        const curQuotient = Math.floor(remainder / den)
        decimalPoint.push(String(curQuotient))
        remainder %= den
    }
    result += decimalPoint.join("")
    return result
};