[LeetCode] 1015. Smallest Integer Divisible by K

https://leetcode.com/problems/smallest-integer-divisible-by-k/

Smallest Integer Divisible by K - LeetCode

Smallest Integer Divisible by K - Medium

 

 

어떤 수 k가 주어진다. 1로만 이루어진 수를 k로 나누었을때, 나누어 떨어지는 수 중 가장 작은 수의 길이를 구하는 문제다. 나누어 떨어지지 않을 경우 -1을 출력한다.

 

11은 1*10 +1 이고,

111은 11*10 + 1 이다.

이를 이용하면 11을 k로 나눈다는 것은, (1*10 + 1) 을 k로 나누는 것이고, 나누어 떨어진다는 것은 나머지가 0이라는 것이므로, (1*10 + 1)%k 를 살펴보면 된다.

(1*10 + 1)%k는 (((1%k) * (10%k))%k + 1%k)%k 로 쓸 수 있다.

이 나머지들을 map을 이용해 저장하고, 구한 나머지가 한번이라도 나왔던 나머지라면, 이 후의 수들이 반복된다는 것이므로 -1을 return 해주면 된다.

 

즉, 나머지 r에 처음 1%k 를 저장하고 (r = 1%k)

r==0 이면 return 1을, 아니라면 11을 살펴보면 된다. 이 때, r을 map에 저장시켜준다.

11에서는 r = ((r * (10%k))%k + 1)%k 로 나타낼 수 있고,

역시 r==0 이면 return 2를, 아니라면 r이 map에 있는지 보고, 있다면 return -1을, 아니라면 map에 r을 저장하고 111을 살펴보는 과정을 반복하자. 

 

전체 풀이 코드

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int r=1%k, i=0;
        unordered_map<int, int> chk;
        chk[r] = 1;
        while(r) {
            r = ((r*(10%k))%k + 1)%k;
            if (chk[r]) return -1;
            chk[r]=1;
            i++;
        }
        return ++i;
    }
};