Python으로 K로 나누어 떨어지는 가장 작은 1로만 이루어진 정수 찾기

문제 설명

양의 정수 K가 주어졌을 때, K로 나누어 떨어지면서 오직 숫자 1만으로 구성된 가장 작은 양의 정수 N을 찾고, 그 N의 길이(자릿수)를 반환하는 문제입니다. 만약 조건을 만족하는 N이 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어 입력이 3이라면 출력은 3이 됩니다. 이때 가장 작은 답은 N = 111이며, 111은 3으로 나누어 떨어지면서 1로만 이루어진 수 중 가장 짧은 수이기 때문입니다.

접근 방법

이 문제는 나머지 연산(modular arithmetic)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 1로만 이루어진 수는 1, 11, 111, 1111, ...처럼 자릿수를 하나씩 늘려가며 만들 수 있습니다.
• 실제로 거대한 정수를 직접 만들 필요 없이, 이전 단계의 나머지에 (r * 10 + 1) 연산을 반복 적용하면 현재까지 만든 수를 K로 나눈 나머지를 계속 추적할 수 있습니다.
• 나머지가 0이 되는 순간, 그 시점의 자릿수가 곧 정답이 됩니다.

알고리즘 단계

1. K가 짝수이거나 K가 5로 나누어 떨어지면 -1을 반환합니다.
2. r := 0, N = 1로 초기화합니다.
3. i를 1부터 K+1까지 반복하면서 다음을 수행합니다.
   • r := (r * 10 + 1) mod k 로 갱신합니다.
   • 만약 r = 0이면 i를 반환합니다.

짝수나 5의 배수를 미리 걸러내는 이유는, 1로만 이루어진 수는 항상 일의 자리가 1이므로 2 또는 5로는 절대 나누어 떨어질 수 없기 때문입니다.

구현 예시

class Solution(object):
    def smallestRepunitDivByK(self, K):
        if K % 2 == 0 or K % 5 == 0:
            return -1
        r = 0
        N = 1
        for i in range(1, K + 1):
            r = (r * 10 + 1) % K
            if r == 0:
                return i

ob = Solution()
print(ob.smallestRepunitDivByK(11))

입력

11

출력

2

결과 분석

입력이 11일 때 출력은 2입니다. 11로 나누어 떨어지는 1로만 이루어진 가장 작은 수가 두 자릿수인 11 자체이기 때문입니다.

시간 복잡도

최대 K번 반복하므로 시간 복잡도는 O(K)이며, 추가로 사용하는 공간은 O(1)입니다. 1로만 이루어진 수를 K로 나눈 나머지는 최대 K가지 값만 존재하므로, 답이 존재한다면 반드시 K번 이내의 반복 안에서 발견됩니다.