SynapSoft Quiz

quiz.py

"""
SynapSoft Quiz
http://www.synapsoft.co.kr/jsp/recruit/1611.html

1/N 모양의 분수를 소수로 나타내어 봅시다.
1/2 = 0.5
1/3 = 0.333333...
1/4 = 0.25
1/5 = 0.2
1/6 = 0.166666...
1/7 = 0.142857142857...
1/99 = 0.01010101010...
위에서 보듯이, 분모가 3, 6, 7, 99 등일 때는 소수점 아래에 같은 숫자가 계속 반복됩니다.
1/2 부터 1/100 까지 이렇게 했을 때, 분모 및 반복되는 부분을 출력하는 프로그램을 작성하세요.
(분모가 2, 4, 5일 때처럼 딱 떨어지는 경우는 출력하지 않습니다)
3 3
6 6
7 142857
9 1
...(중략)...
98 102040816326530612244897959183673469387755
99 10
프로그래밍 언어에 제약은 없지만, 외부 라이브러리는 사용하지 마세요.
"""
import unittest


def find_fraction(n):
    quotients = []
    quotient_index_dict = {}  # (quotient, remainder) -> index in quotients
    divisor = n
    dividend = 1

    while True:
        dividend *= 10
        while dividend < divisor:
            dividend *= 10
            quotients.append(0)

        quotient = int(dividend / divisor)
        remainder = int(dividend % divisor)

        if remainder == 0:
            return 0

        if (quotient, remainder) not in quotient_index_dict:
            quotients.append(quotient)
            quotient_index_dict[(quotient, remainder)] = len(quotients) - 1

            dividend = remainder
        else:
            repeating_start_at = quotient_index_dict[(quotient, remainder)]

            return int("".join([str(i) for i in quotients[repeating_start_at:]]))


class TestFindFraction(unittest.TestCase):
    def test_find_fraction(self):
        self.assertEqual(0, find_fraction(2))
        self.assertEqual(3, find_fraction(3))
        self.assertEqual(6, find_fraction(6))
        self.assertEqual(142857, find_fraction(7))
        self.assertEqual(1, find_fraction(9))
        self.assertEqual(102040816326530612244897959183673469387755, find_fraction(98))
        self.assertEqual(10, find_fraction(99))