[LeetCode] - 728. Self Dividing Numbers

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Self Dividing Numbers" 문제입니다.

--> https://leetcode.com/problems/self-dividing-numbers/description/

 

문제 : 

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0. A self-dividing number is not allowed to contain the digit zero.

Given two integers left and right, return a list of all the self-dividing numbers in the range [left, right].

---

Example 1 :

Input : left = 1, right = 22

Output : [1,2,3,4,5,6,7,8,9,11,12,15,22]

 

Example 2 :

Input : left = 47, right = 85

Output : [48,55,66,77]

 

Constraints : 1 <= left <= right <= 10^4

---

셀프-디바이딩(Self-Dividing) 숫자는 각 자리의 숫자로 모두 나눌 수 있는 숫자입니다. 또한, 숫자 0을 포함해서는 안 됩니다.

예를 들어, 128은 셀프-디바이딩 숫자입니다. 이유는 다음과 같습니다:

• 128 % 1 == 0 (1로 나누어 떨어짐)
• 128 % 2 == 0 (2로 나누어 떨어짐)
• 128 % 8 == 0 (8로 나누어 떨어짐)

주어진 두 정수 left와 right 사이의 모든 셀프-디바이딩 숫자를 반환하는 문제입니다.

 

class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> SDNList = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            if (selfDivisible(i)) {
                SDNList.add(i);
            }
        }
        return SDNList;
    }

    public static boolean selfDivisible(int num) {
        int originalNum = num; // Store the original number for modulus operation
        
        while (num > 0) {
            int digit = num % 10;
            // If the digit is 0 or the original number is not divisible by this digit, return false
            if (digit == 0 || originalNum % digit != 0) {
                return false;
            }
            num /= 10;
        }
        
        return true;
    }
}

 

이 코드는 주어진 범위 내에서 모든 **셀프-디바이딩 숫자(Self-Dividing Numbers)**를 찾고 그 숫자를 리스트로 반환합니다. 셀프-디바이딩 숫자는 숫자 자체가 포함된 각 자릿수로 나누어 떨어지는 숫자를 의미하며, 0을 포함하면 안 됩니다.

1. 리스트 초기화 :
   • 셀프-디바이딩 숫자를 저장할 리스트 SDNList를 초기화합니다.
2. 범위 내 숫자 순회 :
   • left부터 right까지의 모든 숫자에 대해 루프를 돌면서 각 숫자가 셀프-디바이딩인지 확인합니다.
   • selfDivisible(i) 메서드를 사용하여 숫자가 셀프-디바이딩인지 판단합니다. 셀프-디바이딩 숫자인 경우 SDNList에 추가합니다.
3. 셀프-디바이딩 여부 검사 (selfDivisible 메소드) :
   • int originalNum = num; : 원래 숫자를 저장하여 각 자릿수로 나누기 위해 사용합니다.
   • while (num > 0) : 숫자가 0이 될 때까지 각 자릿수를 추출하고 검사합니다.
     • int digit = num % 10; : 현재 자리수를 추출합니다.
     • if (digit == 0 || originalNum % digit != 0) : 자릿수가 0이거나 숫자가 자릿수로 나누어 떨어지지 않으면 false를 반환합니다.
     • num /= 10; : 다음 자릿수를 검사하기 위해 숫자를 10으로 나눕니다.
   • 모든 자릿수가 조건을 만족하면 true를 반환하여 셀프-디바이딩 숫자로 간주합니다.
4. 결과 반환 :
   • 셀프-디바이딩 숫자를 담고 있는 리스트 SDNList를 반환합니다.

시간 복잡도

• O(n * m) : 여기서 n은 주어진 범위의 길이인 right - left + 1이고, m은 각 숫자의 평균 자릿수입니다.
  • 각 숫자에 대해 자릿수의 개수만큼 반복문이 돌아가므로 O(n * m)입니다.
  • 최대 자릿수는 약 4(10,000의 자릿수)입니다.

공간 복잡도

• O(k) : 여기서 k는 결과 리스트에 저장되는 셀프-디바이딩 숫자의 개수입니다.
  • 결과 리스트 SDNList가 차지하는 공간입니다.

SDN은 제가 매번 Self Dividing Number라고 쓰기 귀찮아서 줄임말로 나타낸 것입니다. 그리고 selfDivisible 메소드도 사실 그냥 한 번에 쓸 수 있었지마는 가독성을 높이고 또 서로의 역할을 더 명확하게 나타내기 위해서 다른 메소드로 짠 거뿐입니다. 객체지향언어를 이럴 때 더 잘 활용해야죠.

---

코드 Runtime 결과