백준 / 책 페이지 / 1019번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 책 페이지 / 1019번 (플래티넘 5단계)

문제 사이트: https://www.acmicpc.net/problem/1019

 

문제 설명

---

나의 풀이

import sys

def count_digits_in_range(start, end):
    """
    주어진 범위(`start`부터 `end`까지)의 숫자에서 각 자리 숫자(0-9)가 몇 번 등장하는지 계산합니다.

    Args:
        start (int): 범위의 시작 숫자.
        end (int): 범위의 끝 숫자.

    Returns:
        list: 각 인덱스에 해당 숫자의 등장 횟수를 담은 리스트.
    """
    counts = [0] * 10
    point = 1

    def add_digits(num, point):
        """숫자 하나의 각 자리수를 계산하여 `counts`에 추가."""
        while num > 0:
            counts[num % 10] += point
            num //= 10

    while start <= end:
        # `end`를 10의 배수 - 1로 조정
        while end % 10 != 9 and end >= start:
            add_digits(end, point)
            end -= 1

        # `start`를 10의 배수로 조정
        while start % 10 != 0 and start <= end:
            add_digits(start, point)
            start += 1

        if start > end:
            break

        # 10의 자리수에 대해 각 숫자의 개수 계산
        start //= 10
        end //= 10
        for i in range(10):
            counts[i] += (end - start + 1) * point

        point *= 10

    return counts

if __name__ == "__main__":
    # 입력 받기
    end = int(sys.stdin.readline().strip())

    # 1부터 `end`까지 각 숫자의 개수 계산
    digit_counts = count_digits_in_range(1, end)

    # 결과 출력
    print(" ".join(map(str, digit_counts)))

1. 자리수별 숫자 빈도 계산

주어진 범위 [S,E]에서 특정 자리수 d(0~9)가 등장하는 횟수는 다음으로 계산할 수 있습니다.

여기서 k는 자리수의 위치 (1의 자리, 10의 자리, ...)를 나타냅니다.

2. 각 자리의 숫자 빈도 계산

d가 k-번째 자리에서 등장하는 빈도는 다음과 같이 계산됩니다

추가 조정값: 10의 배수로 정렬되지 않은 경우, S와 E에서 남은 숫자를 별도로 처리합니다.

3. 종합 계산

모든 자리수에 대해 반복적으로 위 계산을 적용하며, S와 E가 10의 배수로 조정되므로 반복적으로 축소됩니다.

---

※ 알아야 할 것

그냥 풀면 시간 복잡도 초과한다!