[리트코드] 3345 - Smallest Divisible Digit Product I

3345. Smallest Divisible Digit Product I

Easy

---

You are given two integers n and t. Return the smallest number greater than or equal to n such that the product of its digits is divisible by t.

 

Example 1:

Example 2:

 

Constraints:

• 1 <= n <= 100
• 1 <= t <= 10

분류

수학, 완전 탐색

---

문제 풀이

문제 분석

이 문제는 두 정수 n과 t가 주어졌을 때, n보다 크거나 같은 가장 작은 정수를 찾는 것입니다. 조건은 해당 정수의 각 자릿수의 곱이 t로 나누어떨어져야 한다는 것입니다.

• 입력: 정수 n (1 ≤ n ≤ 100), 정수 t (1 ≤ t ≤ 10)
• 출력: 조건을 만족하는 가장 작은 정수 (n 이상)

예를 들어 n=15, t=3일 때:

• 15의 자릿수 곱: 1 × 5 = 5 → 3으로 나누어떨어지지 않음
• 16의 자릿수 곱: 1 × 6 = 6 → 3으로 나누어떨어짐 → 정답은 16

---

접근 방법

완전 탐색 (Brute Force) 방식을 사용했습니다.

이유는 다음과 같습니다:

1. 제약 조건이 매우 작음: n의 최댓값이 100이고, t의 최댓값이 10입니다.
2. 답이 존재하는 것이 보장됨: 최악의 경우 0이 포함된 숫자(예: 100, 110 등)를 만나면 자릿수 곱이 0이 되어 어떤 t로도 나누어떨어집니다.
3. 단순 구현이 가능: n부터 1씩 증가시키며 조건을 확인하는 직관적인 로직으로 충분합니다.

자릿수 곱을 계산할 때 문자열로 변환하여 각 문자를 순회하는 방식을 사용했는데, 이는 파이썬에서 가장 간결하고 가독성이 좋은 방법입니다.

---

구현 설명

1. 무한 루프로 후보 숫자 탐색 시작

while True:

• n부터 시작하여 조건을 만족하는 숫자를 찾을 때까지 계속 증가시킵니다.
• 제약 조건상 반드시 답을 찾게 되어 있으므로 무한 루프가 안전합니다.

2. 현재 숫자의 자릿수 곱 계산 및 조기 종료

check = 1
for num in str(n):
    check *= int(num)
    if check % t == 0:
        return n

• check 변수에 자릿수 곱을 누적합니다.
• 핵심 최적화: 곱을 계산하는 도중에 check % t == 0이 되면 즉시 n을 반환합니다.
• 모든 자릿수를 다 곱할 필요 없이 중간에 조건을 만족하면 바로 종료하여 불필요한 연산을 줄입니다.
• 자릿수에 0이 포함되면 check가 0이 되어 즉시 조건을 만족하므로 빠르게 처리됩니다.

3. 다음 후보 숫자로 이동

n += 1

• 현재 숫자가 조건을 만족하지 못하면 n을 1 증가시켜 다음 숫자를 검사합니다.

---

⏱복잡도 분석

시간 복잡도: O(K × D)

• K: 정답이 될 때까지 검사하는 숫자의 개수 (최악의 경우 상수 수준, n ≤ 100)
• D: 숫자의 자릿수 (최대 3자리)
• 제약 조건이 작아 실제로는 상수 시간 O(1)에 가깝게 동작합니다.

공간 복잡도: O(D)

• str(n)로 문자열 변환 시 자릿수만큼의 공간 사용 (최대 3문자)
• 추가 자료구조를 사용하지 않으므로 상수 공간 O(1)로 볼 수 있습니다.

---

핵심 포인트

1. 작은 제약 조건 활용: n ≤ 100, t ≤ 10이라는 매우 작은 범위 덕분에 브루트 포스가 정석 풀이입니다.
2. 자릿수 곱 계산 중 조기 종료: 모든 자릿수를 다 곱한 후 검사하지 않고, 곱하는 도중에 나누어떨어지면 즉시 반환하여 효율을 높였습니다.
3. 0의 특수성 이용: 자릿수에 0이 포함되면 곱이 0이 되어 어떤 t로도 나누어떨어진다는 점을 자연스럽게 처리합니다 (별도 예외 처리 불필요).

풀이 코드

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        while True:
            check = 1
            for num in str(n):
                check *= int(num)
                if check % t == 0:
                    return n

            n += 1