문제
단위분수 중에는 유한소수가 되는 것(1/4 = 0.25)도 있고, 끝없이 반복되는 순환소수가 되는 것도 있습니다. 1/6 = 0.1666...은 한 자리짜리 순환마디가, 1/7 = 0.142857142857...은 여섯 자리짜리 순환마디가 반복됩니다. d = 2, 3, ..., limit 중에서 1/d의 순환마디가 가장 긴 d를 찾으세요. 손으로 하는 나눗셈을 코드로 그대로 옮기면 됩니다. 같은 나머지가 다시 나오는 순간부터 숫자가 반복됩니다.
longest_recurring_cycle(limit) 함수를 구현하세요.
입력
limit: 시도할 가장 큰 분모입니다.
출력
순환마디가 가장 긴 d를 반환합니다. 유한소수의 순환마디 길이는 0입니다. 여러 d가 같으면 가장 작은 값을 반환합니다.
제약 조건
2 ≤ limit ≤ 2000
예시
입력:
limit = 8
예상 출력:
expected = 7
입력:
long long limit = 8;
예상 출력:
long long expected = 7;
입력:
long limit = 8;
예상 출력:
long expected = 7;
설명
2부터 8까지의 순환마디 길이는 0, 1, 0, 0, 1, 6, 0이므로 답은 7입니다.
입력:
limit = 5
예상 출력:
expected = 3
입력:
long long limit = 5;
예상 출력:
long long expected = 3;
입력:
long limit = 5;
예상 출력:
long expected = 3;
설명
1/3은 한 자리가 반복되고 1/2, 1/4, 1/5는 유한소수이므로 답은 3입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
1/d의 새로운 자리는 나머지에 10을 곱한 값에서 나옵니다.
힌트 2
각 나머지가 처음 나온 단계를 기록해 두세요.
힌트 3
나머지가 0이 되면 유한소수입니다. 그렇지 않으면 같은 나머지가 두 번 나온 단계의 차이가 순환마디의 길이입니다.
예상 복잡도
시간 O(limit²), 추가 공간 O(limit)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.