파이썬으로 특정 범위 내 숫자의 등장 횟수 구하기

두 개의 양의 정수 n과 d가 주어졌다고 가정해 봅시다. 여기서 d는 0부터 9 사이의 한 자리 숫자입니다. 우리가 구해야 할 것은 1부터 n까지의 정수 안에 숫자 d가 총 몇 번 등장하는지입니다.

문제 예시

예를 들어 n = 45, d = 5가 입력으로 주어진다면, 출력 결과는 5가 됩니다.

그 이유는 1부터 45 사이의 숫자 중 5라는 자릿수를 포함하는 숫자가 다음과 같기 때문입니다.

[5, 15, 25, 35, 45]

해결 접근 방법

이 문제를 효율적으로 해결하기 위해 다음 단계를 따릅니다.

solve() 함수를 정의합니다. 이 함수는 n과 d를 입력값으로 받습니다.
n < 0인 경우 0을 반환합니다. 이는 재귀 호출의 종료 조건 역할을 합니다.
k := (n / 10)의 내림 값 − 1로 설정합니다.
ans := solve(k, d) * 10 + k + 1로 계산합니다. 이 부분은 재귀적으로 상위 자릿수 범위의 발생 횟수를 누적합니다.
d가 0과 같다면 ans에서 1을 뺍니다. 0은 선행 자릿수로 나타나지 않기 때문입니다.
m := (n / 10)의 내림 값 * 10으로 설정하여 현재 처리 중인 십의 자리 경계를 구합니다.
m이 n 이하인 동안 다음을 반복합니다.
- ans에 m의 문자열 표현에서 d의 문자열 표현이 등장하는 횟수를 더합니다.
- m을 1 증가시킵니다.
최종적으로 ans를 반환합니다.

메인 부분에서는 solve(n, d)를 호출한 뒤 그 결과값을 출력하면 됩니다.

구현 예제 코드

class Solution:
    def solve(self, n, d):
        if n < 0:
            return 0
        k = n // 10 - 1
        ans = self.solve(k, d) * 10 + k + 1
        if d == 0:
            ans -= 1
        m = n // 10 * 10
        while m <= n:
            ans += str(m).count(str(d))
            m += 1
        return ans

ob = Solution()
print(ob.solve(45, 5))

입력

45, 5

출력

코드 동작 원리 설명

이 알고리즘의 핵심은 재귀 호출을 활용해 큰 범위를 작은 단위로 분할 처리하는 것입니다. solve(k, d) * 10 부분은 이미 계산된 하위 범위의 결과를 활용해 전체 발생 횟수를 빠르게 확장하며, 마지막 while 루프는 현재 십의 자리 경계부터 n까지 남은 숫자들만 직접 검사합니다.

또한 d == 0일 때 ans에서 1을 빼는 이유는, 실제 숫자 표현에서는 "05", "005"처럼 앞자리에 0이 붙지 않기 때문에 재귀 계산 과정에서 잘못 포함된 0 하나를 보정해 주어야 하기 때문입니다.

이러한 방식은 단순히 1부터 n까지 모든 숫자를 일일이 확인하는 방법(O(n) 시간 복잡도)보다 훨씬 효율적이며, n이 매우 큰 경우에도 빠른 실행 속도를 보장합니다.