77일 (2269. Find the K-Beauty of a Number) String

The k-beauty of an integer num is defined as the number of substrings of num when it is read as a string that meet the following conditions:

• It has a length of k.
• It is a divisor of num.

Given integers num and k, return the k-beauty of num.

Note:

• Leading zeros are allowed.
• 0 is not a divisor of any value.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: num = 240, k = 2
Output: 2
Explanation: The following are the substrings of num of length k:
- "24" from "240": 24 is a divisor of 240.
- "40" from "240": 40 is a divisor of 240.
Therefore, the k-beauty is 2.

Example 2:

Input: num = 430043, k = 2
Output: 2
Explanation: The following are the substrings of num of length k:
- "43" from "430043": 43 is a divisor of 430043.
- "30" from "430043": 30 is not a divisor of 430043.
- "00" from "430043": 0 is not a divisor of 430043.
- "04" from "430043": 4 is not a divisor of 430043.
- "43" from "430043": 43 is a divisor of 430043.
Therefore, the k-beauty is 2.

 

 

- 접근방법

 

num를 길이가 k의 부분문자열들을 만들고 num을 길이가 k인 부분문자열("43", "30", "00", "04", "43")로 각각 나눴을때 나누어떨어지는 경우의 수를 리턴하면 된다.

 

문자열 변환없이 정수만으로 접근하였다. Example 2를 예시로 사용하겠다.

 

 

1. while문의 종료조건 생성 (cnt)

만약 num = 6, k =2이라면? 5개의 부분문자열이 생성된다.

만약 num = 6, k =3이라면? 4개의 부분문자열이 생성된다.

만약 num = 6, k =4이라면? 3개의 부분문자열이 생성된다.

num의 자릿수 - (k-1) 개의 부분문자열이 생성된다.

 

 

2. 부분문자열을 정수로 구하기 (subNum)

num % 10^k 로 부분문자열 1개를 구하고 num / 10 로 범위를 한칸 옮겼다.

 

예를들어 num = 430043, k =2 라면?

430043 % 10^2(100) = 43

num = 430043/10

 

43004 % 100 = 4

num = 43404 / 10

 

4340 % 100 = 0

num = 4340 / 10

....

subNum들은 43, 4, 0 ... 이다.

 

 

3. 마무리

2번의 경우 num을 직접적으로 num /= 10을 하므로 원래의 수가 아니게된다.

따라서 num을 복사한 copyNum을 이용하여 부분정수(subNum)을 구하고

 

subNum을 모두 구한 후, num % subNum == 0일때 k-beauty의 개수를 세서 리턴한다.

 

 

- 코드

class Solution {
    public int divisorSubstrings(int num, int k) {
        int answer = 0;
        int copyNum = num;
        int temp = (int)Math.pow(10, k);
        int cnt = (int)Math.log10(num) + 2 - k; // 1. 접근방법1 종료조건

        while(cnt > 0) {
            int subNum = copyNum % temp; // 2. subNum들을 구하기위해 copyNum이 희생된다.
            if(subNum != 0) answer += num%subNum == 0? 1 : 0; // 3. k-beauty 개수 세기
            copyNum /= 10;
            cnt--;
        }

        return answer;
    }
}

 

문자열 변환을 의도로 만든 문제인데 문자열 변환을 하지 않아서 매우 빠르다.

전역변수를 지운다면 공간복잡도도 확보할 수 있지만, 복잡해지기 때문에 그렇게는 하기 힘들 것 같다..

 

아참 정수의 자릿수 세려면 Math.log10(1000)+1 = 4; 이 방법이 좋다. (int로 쓴다면 10^9, 10자리까지 가능하니 주의)

 

 

 

https://leetcode.com/problems/find-the-k-beauty-of-a-number/

Find the K-Beauty of a Number - LeetCode