1. 문제 소개

1015. Smallest Integer Divisible by K

2. 나의 풀이

간단하게 마지막 숫자가 1인 수를 나눌 수 없는 2와 5을 제외하고 modulo를 사용해서 풀었다.
처음에는 ans %= k를 넣지 않아서 시간이 너무 늘었었는데, 추가하므로서 빠른 시간에 풀 수 있었다.
시간복잡도는 $O(k)$이다.

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:       # k가 2 또는 5의 배수면 절대로 111..1 형태의 수로 나누어떨어질 수 없음
            return -1
        
        ans, l = 1, 1                     # ans: 현재 repunit mod k, l: 길이
        while ans % k != 0:               # repunit R_l이 k로 안 나누어떨어지면 계속 반복
            ans *= 10                     # R_{l+1} = R_l * 10 + 1
            ans += 1
            ans %= k                      # overflow 방지 및 효율을 위해 mod만 유지
            l += 1                        # repunit의 길이 1 증가
            # print(ans, l)               # (디버깅용)
        return l                          # l이 곧 가장 짧은 repunit 길이

3. 다른 풀이

다른 풀이도 나와 비슷하다.
대신 길이가 k 초과인 경우 동작을 멈추는 과정이 추가되었다.

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:      # 2 또는 5의 배수라면 111...1 형태의 수는 절대 나누어떨어지지 않음
            return -1

        rem = 1 % k                       # 첫 repunit(=1)의 나머지를 계산하여 저장
        len = 1                           # repunit의 길이(현재는 '1'이므로 길이 1)

        while rem > 0:                    # 나머지가 0이 될 때까지 반복
            rem = (rem * 10 + 1) % k      # 다음 repunit: R = (R * 10 + 1) % k (overflow 방지)
            len += 1                      # repunit 길이 증가

            if len > k:                   # 나머지는 최대 k가지 상태 → k번 이상 반복되면 순환 발생 ⇒ 불가능
                return -1

        return len                        # 나머지가 0이 된 순간의 길이가 정답

4. 마무리

mod를 사용하면 쉬운 문제였다. 단지 일의 자리가 1인 숫자를 나눌 수 없는 경우만 생각하면 됐다.